2012年8月30日 星期四

翻譯:the free lunch is over

http://www.gotw.ca/publications/concurrency-ddj.ht m
好文共享,硬體的極限與未來軟體的挑戰
其實這是一篇有點老的文章(2009),想說就提個大概內容,加一些個人的解釋,分享一下。

--

CPU已經來到極限了,我們曾經在摩爾定律下,每18個月把transistor的數量加一倍,享用更快的處理速度,更佳的效能;很可惜的,硬體效能增加的同時,我們的軟體也進一步吃光所有多出來的效能,更多的供給推出更大的需求,以前我們只要計算機幫我們算答案,現在我們卻要手機和我們對話。

硬體製造商急於推出更快的產品,在各種方法上用盡心力。

但在三個推動CPU加速的關鍵:clock speed, execution optimization, cache,都遇到各自的問題。

首先是clock speed:
clock是數位晶片的心臟(或說動力,你要說查克拉也可以),每一個運算單元靠clock來同步資料的寫入、運算和輸出,理論上,加速clock等效於運算速度的加倍。

但這有極限。

半導體靠的是電位的高與低來表示數位的1與0,每進行一次轉換,都會對電容進行一次充電或放電,clock愈快,充放電的頻率也會更快,相對的就是功耗的提升,理論上,這個功耗和clock的頻率是平方的關係,現在高效CPU的功耗大概都在100W~200W間,這大概跟一台冰箱差不多,這些熱會在大概2~3 cm^2的面積內的產生,通過各種散熱膏、散熱片、風扇帶到晶片外,所以上youtube 查查'cpu cooking' ,你可以找到用CPU烤肉、煎蛋的影片。
http://www.youtube.com/watch?v=7uBNCN6v_gk

甚至還有對記憶體超頻結果把封裝燒掉的影片……
http://www.youtube.com/watch?NR=1&feature=fvwp&v=Gw-rUCwLoQ0

也可以知道…為什麼現在瘋狂的超頻者,甚至要用液態氮來冷卻CPU。
http://www.youtube.com/watch?v=tPzNl1t4Qmk

當然…個人PC大概還不會出現水冷式的系統,目前clock 頻率的上限,大約就在3.6~3.8GHz左右,再上廢熱會超過氣冷式的極限。

另一方面execution optimization希望能在每個cycle中執行更多的instruction,無論是pipeline, branch prediction等等,這裡面有相當複雜、有關硬體設計的思維,但同樣的,能從execution optimization 中榨出的效能也面臨極限,甚至出現過processor會調動write, read的執行序列,以換到更多效能…。
加上更多的cache也是個不錯的方法,以前,記憶體和CPU的速度是相同的,雙方合作良好;後來CPU的運作頻率遠遠超過了記憶體,於是出現了cache來保存CPU運作中需要的資料,CPU得以進行更快的運算。

當上述方法都來到了極限,目前主流都超向另一個方式;利用hyperthreading(超執行緒?), multicore(多核心)的方式來換到更多的速度,這兩種方法其實都不是運算速度的增加,而是用面積來換到一些速度,就像生產線滿載了,就要蓋一家新工廠。
Hyperthrading的作法是複製一些記錄CPU運算狀態的單元,並不包含關鍵的ALU的運算單元,這讓作業系統可以「看到」兩個運算的單元,當其中一個運算單元閒置時(許在等cache或memory的回應),另一個運算單元就可以取用關鍵的運算單元執行運算,就像靈夢休息的時候,魔理沙就會出來接手。

這詳細的可能還是要問晶片設計組的同學們orz。
Hyperthreading需要有作業系統的配合,增加大概5%的面積,可以換到5~15%的效能提升。

multicore就不較沒那麼稀奇,直接複製一套core,讓作業系統去分配,但更多的core絕非效能等比例上升的意思,不是每一個運算都能夠平行的處理,指令間需要shared data時也會加深系統的複雜度。
面對多執行緒和多核心的趨勢,本文作者認為concurrency(多工?同步?)將會是未來軟體的重大變革,未來的程式會在多核心上運行,要如何避免多工上的deadlock和各式新型態的錯誤,事實上我認為這早已是現代進行式,否則我們不會有那麼多多核心的電腦正在運行。

作者在此提出幾點結論:
1.未來軟體設計要能了解何類工作可以平行化處理以加速,哪些不行,並能譔寫相對應的程式。
2.CPU火力無限的時代已經結束了,以前程式速度卡在網路、記憶體、database,這些東西還在進步當中- TLE, SSD... - 但CPU大概已經到了極限,短時間內看不到突破性的可能。
3.承上一點,軟體的optimization將會愈來愈吃重,Vista轉換到win7證明了軟體optimization可以有多大的效能進步,未來軟體將更需要這些。
4.programming language也要面對concurrency的問題,例如,雖然大多數的大型程式以C++為核心,但C++並未將concurrency納入考量,因而需要限於平台的library來處理concurrency的問題;一套統一concurrency問題的標準也亟待發展。

Reference:
Wikipedia about hyperthreading:
http://en.wikipedia.org/wiki/Hyper-threading
CPU power consumption comparison:
http://www.tomshardware.com/reviews/ivy-bridge-benchmark-core-i7-3770k,3181-23.html

2012年8月20日 星期一

不正經,開箱文

最近因為筆電快要解體,不開玩笑,像正面偵測螢幕的按鈕竟然掉下來了。

就趁著八月台北資訊展時入手一台,因為平常要跑很多模擬的程式,需要的是運算力強的機種,本人又是個效能控XD,也不想盯著太小的螢幕,經過綜合評估,最後入手的是這台ACER Aspire V3-571G,近日解禁,於是來寫個不正經的開箱文:

官方網頁:
http://www.acer.com.tw/ac/zh/TW/content/model/NX.RZNTA.002
算是這個系列的頂級機種了,買價是30.8k,pchome上是賣33.4k,差別在pchome有送Dialog3,但那個東西對我價值是0元,如果有送minecraft 帳號或是東方全套我倒是可以考慮一下。

CPU:i7-3610QM,記憶體加到8G,整體而言不重,加上電池2.2kg,比我舊的Aspire 5633還要輕。這裡真的很想表一下…電池可以拆我是很高興啦,但你好歹設計一個備用電池,當我主電池拆下來,插頭又被拔的時候,可以撐個5分鐘;不要插頭一拔,螢幕就瞬間黑掉。

外觀是所謂「鋼琴烤漆材質」,亮到會發光…,不過也超容易沾指紋,我甚至不用燻強力膠就看得到我的指紋了,所以千萬別拿這台筆電當兇器,光指紋就可以釘死你!

15.6大尺寸的螢幕…毫無反應,就只是個螢幕。


鍵盤是所謂的「巧克力鍵盤」,雖然說我不知道為什麼叫巧克力鍵盤,也不能吃又沒味道,不過打起來還頗順手的,聲音有點大。


使用狀況:
打開電腦,內建有預設的windows7,整體windows跑分有5.9,鎖在硬碟的讀取效率


然後windows再見,再來大概很久不會再見了=w=。

我選的linux是Archlinux x86_64
只看CPU的話,效能超讚,在archlinux下跑linux的pi指令,算到小數點下1000000位,用time來記時,用real來比較:
$time pi 1000000 > /dev/null
舊筆電的Intel(R) Core(TM)2 CPU T5500 1.66GHz要8.5秒;桌電的core 2 quad要5.6秒;這台i7只需要1秒啊!


電池也很強,從晚上7點到12點,全程都在跑archlinux安裝,電池很夠,當然也可能是過程中都沒啟動X。
在archlinux下,因為optimus的關係,顯示卡應該還沒連上,灌的時候X搞了很久,後來只用intel driver才進到X裡,真的超想說
nVidia Fuck You!

其實無線網卡也連不上,broadcom bcm57781的卡,自己編譯驅動還有一些錯誤要修…
不過,只灌了Intel-dri就有了不錯的成績,minecraft視野調到far的fps還有50~60,拿來打東方打起來也很順,附個圖。



另外網路上有說這台打Dialog3的時候會有過熱的問題,個人沒打Dialog3,但就算是安裝時,出來的風也沒有很熱;整體給分我給85/100,推薦給有高運算、高效能需求的人;小扣一些主要是三點:
1. 電池設計:
2. 對linux使用者來說,Optimus真的很崩潰…
3. 這台比較新,無線網卡linux好像還沒有支援到,現在linux處於沒無線網路的狀態。
當然如果你用windows就沒什麼差惹。

2012年8月9日 星期四

正規表示法:規則篇


正規表示式(Regular expression, RE)--規則篇:
正規表示式是個強大的工具,定義了明確的定串比對規則,來幫助使用者把梳字串,在很多程式都有支援,如Linux shell grep, awk, sedvi(m)的搜尋取代功能等,C語言的scanf其實也有支援,可惜正規表示法規則甚多,一時之間難以記全。
這篇主要記錄正規表示法的規則,整理自“Practical Programming in Tcl and Tk”第十一章,給自己做個參考:

  1. 一般字元與跳脫字元:
如果要比對字串,最簡單的規則就是:把字元寫出來,當寫:
a,就會比對出a,夠簡單吧。
但這樣就沒啥變化了,如果我要比對a, aa aaaaa...aa呢?如果全部的東西都是直接比對,就少了這種彈性,所以正規表示式定義下例幾個字元為跳脫字元,平時做為特殊處理之用,要比對他們需要特殊規則,包括:
.*+?()|[]^$\
在比對中寫下這些符號的功能之後會一一介紹到,如果是要比對這些符號,就用backslash \ 跳脫。
例如要比對\,就需要寫\\而非只有\

  1. 字組(character sets)及多重選項(alternation)
如果我們要寫一個讓使用者輸入y/n的程式,使用者可能會填y/Y/n/N裡面一個,因此就有了字組的概念,字組利用跳脫字元[],讓某一個位置有多重選項:
[yY],則yY都可以match
[]裡面可以使用“[x-y]”的規則,來比對某區間的字,例如:
[0-9]比對所有數字, [a-z]比對小寫的英文。
這裡要注意的是,隨著語系的選擇,[x-y]會有不同的範圍,不過一般都是以LANG=C的情況下去設計,也就是0-9A-Za-z的排序。
子規則1:反向用[^],例如我要比對“不是<”,就用[^<],如果是[^a-z],就會排除所有小寫英文。
子規則2:比對跳脫字元除了]需要在[]要排第一位、\仍要跳脫外,其他在[]就不用跳脫,直接寫就可以
例如下行會比對出所有的跳脫字符:
[][.*+?()|\\]
另外則是{}這個直接寫就是直接match,但加上\{,\}後則是跳脫為特殊意思。

  1. 數量(quantifiers)比對與比對順序:
如果像上述,我們要比對a,aaaaaaaaa...aa,或者我們只要使用者輸入「o某字z」,他要orz, otz,omz 我才不管呢?
首先使用的是「.」,這是RE中的「任意一個字元」,跟shell的不太一樣,這要小心。
所以上面的比對,我們可以寫 o.z
那針對不同的數量,我們就需要數量字符:*+? 以及{m,n}
字符
代表數量
*
0~∞
+
1~∞
?
0~1
{m,n}
m~n次,其中n可以不填,表示∞
所以說,上面的比對可以用 a+ 完成。
重複的可以用()包起來,[]裡面的重複也OK,將數量字符直接加在下括號的後面即可。
比較重要的是 * 這個符號用起來要小心,這個比對表示任意字符重複0~n次,有時會造成不預期的結果。這就牽扯到正規表示法的比對規則了,如果一個match在字串中有多個相符的比對時,其規則如下:
  1. 各相符比對,最接近開頭者優先:
  2. 如果是一樣的開頭,預設最長者優先,這個可以改換為nongreedy,即較短者優先。
所以如果用 [a-z]* 去比對 123abc,一般可能會預期取出abc,但不對,在123前的開頭的空字串才是優先match的對象,一般都建議用+強制一定要有match來避免這樣的狀況。

  1. 字集(character classes)
字集為一些設定好的字元組合,寫法為:[:identifier:]
整理可選用的identifier如下:

identifier
比對:
等同表示法:
lower
英文小寫
[a-z]
upper
英文大寫
[A-Z]
alpha
英文字母
[A-Za-z]
digit
數字
[0-9]
xdigit
十六進位數字
[0-9a-fA-F]
alnum/print
以上總集合
[0-9a-zA-Z]
punct
標點符號例如 `'”/<>之類


graph
非控制字符或空白類字符,其實就是以上總集合
我猜可以寫成[[:alnum:][:punct:]]
blank
空白和tab
[ \t]
space
空白類字符:空白,換行,回車,tabvertical tabform feed
有人知道後兩個是蝦毀嗎…
\s
cntrl
控制字符:ASCII 0~31


< >
分別比對單定開頭與結尾



  1. 定位字符(anchoring)
這部分兩個定位就是^$ =w=

  1. 反斜線跳脫:
利用反斜線的跳脫字符,可以match一些特殊的字符,主要分為四類:特殊符號類;與字集相同的設定,可以match一個字集;定位字符類;數字指定類,整理如下:
1 特殊符號類:
表示法:
比對:
等同符號表示:
\a
Alert character.


\b
Backspace character.
\u0008
\e
Escape character(ESC)
\u001B
\n
Newline
\u000A
\B
Backslash
\\
\0
NULL
\u0000
\r
Carriage return
\u000D
\t
Horizontal tab
\u0009
\f
Form feed
\u000C
\v
Vertical tab
\u000B
\cx
Control-x



2 字集類:
表示法
比對
等同表示法
\d, \D
數字, 非數字
[[:digit:]] ,[^[:digit:]]
\s, \S
空白類字符,非空白類字符
[[:space:]] , [^[:space:]]
\w, \W
字母+數字+底線, 非以上組合
[[:alnum:]_] , [^[:alnum:]_]

3  定位字符類:
表示法
比對:
\A, \Z
字串開頭, 字串結尾
*還沒找到相對應的範例
\m, \M
單字開頭, 單字結尾 [[:<:]] [[:>:]]
\y, \Y
單字開頭或單字結尾, \y
*還沒找到相對應的範例

4  數字指定類:
表示法:
比對:
\unnnn, \Unnnnnnnn
16-bits, 32-bits Unicode character code.
\xhh Consumes all hex digits after \x.
An 8-bit hexadecimal character code.
\x, \xy, \xyz
xyz為數字,這個可以是back reference,或者是8-bit octal character code

  1. Nongreedy(非貪婪?這怎麼翻(yay))
之前提過RE的規則是愈長愈好,設定Nongreedy即是變成愈短愈好,使用的是? 加在第三項的數量(quantifiers)比對後面,比如說我們要match整個輸入中的第一行,如果寫:
.+\n 這樣會match整個輸入,直到最後一個\n符號,其中包括很多很多換行符號。
.+?\n 設定+nongreedy,則遇到第一個\n就會結束比對
或者我們要抓<title></title>中間的文字:
<title>(.*?)</title>
所有的數量比對加?在後面都會變成non-greedy??代表0次優先,{1,3}?則會以1,2,3的順序去match

  1. Back referencelook ahead
這個規則比較重在要把內容存到暫存裡的狀況,一般的狀況下似乎不太用到。
在正規表示式中除了直接match的結果外,還可以用小括號()來記錄子比對的結果:
例如<title>(.*?)</title>,除了match整段文字外,可以取出兩個tag中間的文字內容。
要取出這個這個比對結果,可以用Back reference,使用的方式是\xx為數字,依數字對應到各子比對結果,子比對結果的排序為“外到內,左到右”,如下所示:
(())(),注意()是包括自己跟()的內容。

另一方面,如果我們只想要比對,卻懶得管一些比對的內容呢?這就需要look ahead,我想到最需要誕個功能的地方是rename,我要改掉所有txt檔,卻只要取出檔名的部分,這時候就需要look ahead'
例如我要取出副檔名為.txt的文件名稱:
^.*\.txt$,可以,但記錄下來的是:lalala.txt.txt是不需要記錄的
positive look ahead^.*(?=\.txt)$,記錄的就只有lalala
negative look ahead^.*(?!\.txt)$,這反過來,比對出非.txt結尾的檔案名稱。
還有一個是(?:pattern),同樣也是不記錄pattern中的內容,但跟look-ahead的差異點在哪我就不是很確定了。

其實主要的功能就上述這些,我覺得主要會用到的大概只到第6點,我在vim會用到第8點,我提的那本書還有兩個功能,一個是collating element [.identifier.],只是書裡沒說得很清楚,我也還沒試出幹什麼用的…;另一個是Equivalent class [=char=],只有比對Unicode例如[=o=]可以比對 o, ō, ŏ,但平常好像也用不到。
這篇主要整理規則,之後會寫一篇有關應用方面的實例與方法。

如果是有關C語言中,有關scanf的部分,可以參考scanf的整理,一些基本的正規表示法語法在scanf中其實是有支援的,請見:

2012年8月7日 星期二

比賽與創業

很有趣的,在大學最後兩年的暑假,分別參加了YEF和Tic100兩個國內大型的創業競賽,雖然說結果都不是很好,YEF最後沒選上代表,tic100進了決賽之後就被刷掉了,不過,在參加完之後,對這類創業競賽也有一些自己的想法和心得,在這裡分享給大家。

首先我必須說,如果你已經有能力,那麼創業競賽不適合你。

Zuckerberg並不需要創業競賽就可以把世界搞得天翻地覆,像我有兩個同學,大四和其他幾個同學約一約,就創了個網站[1],上次還被邀請去參加創業聚會去做海報展示,他們哪需要參加什麼創業比賽,他們需要創投跟完整的創業諮詢;比如說,之前鬧得沸沸湯湯Now.in事件,如果之前就有創業諮詢來為創辦人分析其中的權利爭議,也許就不會誤觸版權地雷。
目前,包括YEF和tic100兩個競賽,用意都不是讓人們真的要去創業的創業競賽,而比較像一種創業的訓練,試著跟不同的領域的隊友合作,去做一個提案,從而去學習創業的不同面相,行銷、財務、技術,無論未來有沒有要創業,這些東西也許都用得上。

所以說,我對參加創業競賽會有幾點建議:

1. 排掉時間,全心投入:
都已經投入了,就全心投入,不要被自己的能力或學歷給限制住了,去學一些以前沒學過的東西,學技術就只做技術不碰財務內容,問題是如果你創業了,這些東西你不碰嗎?跟我同屆的YEF有一組,他們決定:以前不會做投影片的來做投影片,不會簡報的來練簡報,沒學過財務報表的來寫財務報表,可以想見他們這組一定超花時間,每個人不但要學新的內容,還要教會別人其他東西,但比賽結束,他們一定學會了很多東西。
參加一個比賽動輒要花上幾個月的時間,從學期中延伸到暑假,會有很多外務、課業來干擾,參加比賽前一定要想好自己參賽的目的,然後放開心胸好好學習,這樣才會學到最多。

2. 如果你已經參加了兩次創業競賽,為什麼還要參加第三次?
就如我上面說的,台灣的創業競賽大部分都不是要幫助你創業,而是一個訓練的過程,經過兩次的創業競賽之後,對於大部分訓練的內容:商業模式、簡報、財務,應該都有了基本的了解,所以說,如果你已經參加了兩次創業競賽,為什麼還要參加第三次?

參賽很花時間,如果已經有人兩次參賽的經驗,下一步:就直接去創業吧~
其實直接了當的說,就算參加過兩次的創業競賽,對創業這碼子事,還是很茫然;因為實際去創業所面對的困難,遠比競賽模擬的還要多很多,競賽不是真的,去做才是真的。

3. 創業不急,基本功更重要:
最後一個想法,目前幾個創業競賽主打都是科技產業,瞄準的族群是大學、大專生;這一兩年因為網路產業跟App產業興起的關係,這幾年的創業競賽跟創業消息大部分都是App相關。從另一方面來看,網路產業跟App產業技術門檻比較低,相對競爭也遠較其他產業激烈。

在這裡引用一位學長的話:「台灣學生並不缺創新創意,我們缺的是基本功。」

比如說Intel,這是完完全全比基本功的產業;ARM要和Intel競爭,也是在RISC的架構投資了大量的設計,一切都是基本功的累積,排除了大量競爭者的競爭,得到的影響力和回報也高至少一個數量級;上次聽了一個創業小聚有關專作「安全交易晶片」的簡報,只能以嘆為觀止來形容,那完全是不同層次的創業。
在這裡我想舉上次看到的Garmin做例子[2],GPS技術剛起步,其實只有鑽研導航相關的人能夠做實際應用,其他人是沒有機會的,甚至根本看不到這方面的機會,研究的東西不會沒用,只是時候未到。

創業不急,基本功更重要,有基本功才能擁有更多的機會和執行的實力。

以上是幾點個人對創業競賽的想法,參加過競賽,也知道自己離創業還有一段距離,特別是自己在專業技術上的投入還有待加強;tic100結束之後,我也要加入碩士班,之後可能也要先工作幾年,甚至是一輩子工作下去到退休。

上次有學弟問我,你出來之後要做什麼?我直接了當的回答:「創業」,他回傳給我個:「!」XD

的確,回答創業聽起來很威,其實我內心何嘗不是惶恐,不知該如何下手呢?
希望大家都能了解,參加創業競賽未必會創業,也未必要創業,而是知道有創業這條路,這兩年在YEF和tic100種下的種子,希望有一天能發出它們的芽;種子發芽需要時間,創業也是。

[1]:同學的網站幫忙宣傳一下,一個高品質的圖片交易平台,雖然說模式不算很新,不過畫面還滿漂亮的www:
https://www.shotwill.com/
[2]:商業週刊:台灣國際航電
http://www.businessweekly.com.tw/webarticle.php?id=22119