- 每個 tab 使用不同的 process,可以避免某個網頁當機,就造成整個瀏覽器必須關閉
- 使用不同的 process 也可以減少記憶體的 fragment 問題
- 加強的 JavaScript 引擎,執行 JavaScript 的速度大幅提高
- 加強安全性,例如可以將某個 tab 設定為「不記錄」模式,在此 tab 中所有輸入的資料、cookie 等都會在 tab 關閉被刪除
- 開放原始碼
2008年9月3日 星期三
Google 發表新的瀏覽器 Chrome
Google 發表了新的瀏覽器 Chrome。Google 表示,Chrome 主要的特點包括:
2008年8月21日 星期四
2008年6月19日 星期四
NVIDIA 發表配合 GT200 顯示晶片的 CUDA 2.0 beta 版
NVIDIA 發表了配合新的 GT200 顯示晶片的 CUDA 2.0 beta 版,可以在這裡取得。
GT200 顯示晶片是屬於 CUDA compute 1.3(之前 G80 系列是 1.0,而 G84/86/92 則是 1.1)。目前不清楚哪些顯示晶片會是 1.2。根據最新的 programming guide,1.2 新增的功能包括:
Warp vote 則是用來減少同一個 warp 中,因為不同的分支而造成 serialization 的問題。這是因為在 CUDA 中,同一個 warp 的各個 thread 如果有不同的條件分支結果,就會需要 serialize,造成速度上變慢。利用 warp vote,就可以強迫一個 warp 只有一種條件分支結果,以避免 serialization 出現。
另一個值得注意的就是 GT200 的 double precision 運算。根據 Programming Guide 的資料,double precision 的四則運算和平方根,完全符合 IEEE 754 的規範(single precision 的除法和平方根無法符合 754 規範的精確度,因為它是用乘上倒數的方式做的)。這對一些科學計算的應用會比較方便。Double precision 的加法、乘法、和 FMA 也支援 IEEE 754 規定的各種不同的 rounding mode(single precision 只支援 round-to-zero 和 round-to-nearest)。
GT200 顯示晶片是屬於 CUDA compute 1.3(之前 G80 系列是 1.0,而 G84/86/92 則是 1.1)。目前不清楚哪些顯示晶片會是 1.2。根據最新的 programming guide,1.2 新增的功能包括:
- Shared memory 有 atomic 操作功能
- Global memory 的 atomic 操作,增加 64 bits 運算(1.1 只有 32 bits)
- 支援 warp vote
- 每個 MP 暫存器數目加倍至 16,384 個
- 每個 MP 同時可以進行的 warp 數目增加到 32 個(原為 24 個)
- 每個 MP 同時可以進行的 thread 數目增加到 1024 個(原為 768 個)
- 增加 double precision 的支援
Warp vote 則是用來減少同一個 warp 中,因為不同的分支而造成 serialization 的問題。這是因為在 CUDA 中,同一個 warp 的各個 thread 如果有不同的條件分支結果,就會需要 serialize,造成速度上變慢。利用 warp vote,就可以強迫一個 warp 只有一種條件分支結果,以避免 serialization 出現。
另一個值得注意的就是 GT200 的 double precision 運算。根據 Programming Guide 的資料,double precision 的四則運算和平方根,完全符合 IEEE 754 的規範(single precision 的除法和平方根無法符合 754 規範的精確度,因為它是用乘上倒數的方式做的)。這對一些科學計算的應用會比較方便。Double precision 的加法、乘法、和 FMA 也支援 IEEE 754 規定的各種不同的 rounding mode(single precision 只支援 round-to-zero 和 round-to-nearest)。
2008年4月17日 星期四
ASIRRA
有使用過網頁郵件或是一些網路討論區的人都會知道,有一種叫 CAPTCHA 的東西。CAPTCHA 是利用把隨機產生的文字經過一些扭曲、加上雜訊等動作之後的圖片,讓使用者去進行判讀,主要目的是要避免那種自動化的程式大量申請網頁郵件帳號或網路討論區帳號,再利用這些帳號來散播廣告信件。
很明顯的 CAPTCHA 的有效性,是基於「人類可以判讀」而「電腦不容易判讀」的假設之上。但是,現在電腦判讀 CAPTCHA 的能力愈來愈強,而且有些 CAPTCHA 已經混亂到人都不太容易看得清楚了。因此,這已經是一個相當嚴重的問題。最近的一些報導中顯示,包括 Gmail 和 Hotmail 的 CAPTCHA 系統都已經被有效率的破解,甚至達到平均一分鐘即可自動建立一個帳號的效率。
為了解決這個問題,也有很多人想過不同的方法。一個很明顯的「人類很擅長」而「電腦很不容易做」的工作,是圖片的辨識。其中一個例子是 KittyAuth 系統。KittyAuth 會隨機選出不同的動物的圖片,並要求使用者選出貓咪的圖片。理論上電腦很難判斷一張動物的照片是不是貓咪,所以可以達到分辨人類和電腦的效果。
不過 KittyAuth 和其它類似的系統都有同樣的缺點:他們的圖片資料庫的大小不夠。這使得破解變得容易:電腦不需要真的去判斷哪些照片是貓咪,它只需要「記住」哪些照片是貓咪就好了。如果照片都沒有經過任何更改,可以很容易利用 MD5 等 signature 比對的方式,就可以快速判斷一張照片是否在資料庫中。當然,一個解決方法是把照片進行細微的改動,例如加上一些雜訊。不過即使如此,如果資料庫不大(例如數百張照片),要比對兩張照片是否相似,也不是困難的事情。
為了解決這個問題,Microsoft Research 提出了一個叫 ASIRRA 的系統。基本上 ASIRRA 和 KittyAuth 一樣,也是使用動物的照片,要求使用者選出哪些是貓咪。不過,和 KittyAuth 不同的是,ASIRRA 和 Petfinder.com 合作。Petfinder.com 是一個幫無家可歸的寵物找到新家的服務,他們有數百萬張不同動物的照片。因此,ASIRRA 系統可以解決 KittyAuth 等系統的最大問題,即資料庫大小有限的問題。另外,為了避免電腦程式利用亂猜的方式,ASIRRA 要求使用者選出所有貓咪的圖片,而不是只選出其中一張。例如,12 張照片中,如果有未知數目的貓咪照片,則一個亂猜的程式,正確選出所有貓咪照片的機率,只有 1/4096。
那麼 Petfinder.com 能得到什麼好處呢?ASIRRA 在每張動物的照片下,增加一個 "Adopt Me" 的連結,讓有興趣的使用者,可以選擇領養照片中的動物。這同時也讓 Petfinder.com 可以大量增加其動物照片的曝光率。
目前 Microsoft Research 提供 ASIRRA 供大眾進行 beta 測試。不過這樣的系統倒底是不是真的有效呢?恐怕也很難說,畢竟理論上數百萬張照片,仍有機會透過人工方式進行分辨(畢竟這些照片一開始也是以人工方式進行分辨的)。想要破解 ASIRRA 的人,可以儘可能收集到足夠多的照片資料,以人工進行分辨後,即使沒辦法達到 100% 成功率,但若有 80% 成功率,也可以大幅提高猜對的機率(12 張照片若有 80% 猜對機率,則完全正確選中的機率會提高到 1/15)。
另一種可能的方式,是透過圖片合成。最簡單的方法,是把大量動物的照片,經過去背處理,再隨機以不同的大小,甚至不同的角度,貼在隨機的背景上(例如類似草皮的圖案)。然後,再要求使用者點選在貓咪上。為了降低亂猜的成功率,可以要求使用者需連續答對一定的次數。這樣一來,即使想要破解的人,已經取得完整經過去背處理的照片資料庫,要比對出貓咪的位置,仍會需要費一番功夫。另一種方法則是利用 3D 繪圖技術,從隨機的角度繪製不同的 3D 物品,同樣是貼在隨機的背景上,再要求使用者選出指定的物品。不過,這樣做的話,伺服器的負擔可能會變得很重。
很明顯的 CAPTCHA 的有效性,是基於「人類可以判讀」而「電腦不容易判讀」的假設之上。但是,現在電腦判讀 CAPTCHA 的能力愈來愈強,而且有些 CAPTCHA 已經混亂到人都不太容易看得清楚了。因此,這已經是一個相當嚴重的問題。最近的一些報導中顯示,包括 Gmail 和 Hotmail 的 CAPTCHA 系統都已經被有效率的破解,甚至達到平均一分鐘即可自動建立一個帳號的效率。
為了解決這個問題,也有很多人想過不同的方法。一個很明顯的「人類很擅長」而「電腦很不容易做」的工作,是圖片的辨識。其中一個例子是 KittyAuth 系統。KittyAuth 會隨機選出不同的動物的圖片,並要求使用者選出貓咪的圖片。理論上電腦很難判斷一張動物的照片是不是貓咪,所以可以達到分辨人類和電腦的效果。
不過 KittyAuth 和其它類似的系統都有同樣的缺點:他們的圖片資料庫的大小不夠。這使得破解變得容易:電腦不需要真的去判斷哪些照片是貓咪,它只需要「記住」哪些照片是貓咪就好了。如果照片都沒有經過任何更改,可以很容易利用 MD5 等 signature 比對的方式,就可以快速判斷一張照片是否在資料庫中。當然,一個解決方法是把照片進行細微的改動,例如加上一些雜訊。不過即使如此,如果資料庫不大(例如數百張照片),要比對兩張照片是否相似,也不是困難的事情。
為了解決這個問題,Microsoft Research 提出了一個叫 ASIRRA 的系統。基本上 ASIRRA 和 KittyAuth 一樣,也是使用動物的照片,要求使用者選出哪些是貓咪。不過,和 KittyAuth 不同的是,ASIRRA 和 Petfinder.com 合作。Petfinder.com 是一個幫無家可歸的寵物找到新家的服務,他們有數百萬張不同動物的照片。因此,ASIRRA 系統可以解決 KittyAuth 等系統的最大問題,即資料庫大小有限的問題。另外,為了避免電腦程式利用亂猜的方式,ASIRRA 要求使用者選出所有貓咪的圖片,而不是只選出其中一張。例如,12 張照片中,如果有未知數目的貓咪照片,則一個亂猜的程式,正確選出所有貓咪照片的機率,只有 1/4096。
那麼 Petfinder.com 能得到什麼好處呢?ASIRRA 在每張動物的照片下,增加一個 "Adopt Me" 的連結,讓有興趣的使用者,可以選擇領養照片中的動物。這同時也讓 Petfinder.com 可以大量增加其動物照片的曝光率。
目前 Microsoft Research 提供 ASIRRA 供大眾進行 beta 測試。不過這樣的系統倒底是不是真的有效呢?恐怕也很難說,畢竟理論上數百萬張照片,仍有機會透過人工方式進行分辨(畢竟這些照片一開始也是以人工方式進行分辨的)。想要破解 ASIRRA 的人,可以儘可能收集到足夠多的照片資料,以人工進行分辨後,即使沒辦法達到 100% 成功率,但若有 80% 成功率,也可以大幅提高猜對的機率(12 張照片若有 80% 猜對機率,則完全正確選中的機率會提高到 1/15)。
另一種可能的方式,是透過圖片合成。最簡單的方法,是把大量動物的照片,經過去背處理,再隨機以不同的大小,甚至不同的角度,貼在隨機的背景上(例如類似草皮的圖案)。然後,再要求使用者點選在貓咪上。為了降低亂猜的成功率,可以要求使用者需連續答對一定的次數。這樣一來,即使想要破解的人,已經取得完整經過去背處理的照片資料庫,要比對出貓咪的位置,仍會需要費一番功夫。另一種方法則是利用 3D 繪圖技術,從隨機的角度繪製不同的 3D 物品,同樣是貼在隨機的背景上,再要求使用者選出指定的物品。不過,這樣做的話,伺服器的負擔可能會變得很重。
NVIDIA 發表 CUDA 2.0 beta 版
NVIDIA 發表了 CUDA 2.0 beta 版的 Toolkit 和 SDK。這一版主要新增的功能,是對 Windows Vista 的支援(包括 32 bits 和 64 bits 版本)。NVIDIA 目前沒有提到其它 2.0 版新增的功能包括哪些,但大致上看起來,2.0 版包括了新的文件檔(其中包括一個使用 chm 格式、較容易查詢的 CUDA Reference Manual),以及新的 sample。比較細節上的新功能,目前看起來包括 3D 貼圖的支援,以及 cudaGetDeviceProperties 增加了 multiprocessor 數目以及 device 是否支援重疊操作的欄位。
CUDA 2.0 beta 可以在這裡下載
CUDA 2.0 beta 可以在這裡下載
2007年11月25日 星期日
Mahalanobis 的問題
在 Wikipedia 上介紹數學天才 Ramanujan 的文章中,提到一個有趣的問題:
假設你在一條街道上,有 n 間房子,路牌號碼是 1 ~ n。其中有一間房子(號碼 x),它的左邊所有房子的路牌號碼總和,和它右邊的房子的路牌號碼總和相同。如果 n 在 50 至 500 之間,那麼 n 和 x 各是多少?
文章中提到 Ramanujan 很快就利用連分數解出了這個問題,讓他的室友 Mahalanobis 非常驚訝。
當然,Ramanujan 是數學天才。不過這個問題讓我覺得很有意思:它看起來算是相當簡單,我想可能小學生也能聽懂。不過這個問題倒底要怎麼解呢?
考慮 x 左邊的房子,即號碼 1 ~ x-1 的房子,其路牌號碼總和就是 x(x-1)/2。它右邊的房子,路牌號碼總和是 n(n+1)/2 - x(x+1)/2。這兩個數字要一樣,所以:
x(x-1)/2 = n(n+1)/2 - x(x+1)/2
-> x^2 = n(n+1)/2
所以,問題變成,要找出一個平方數(即 x^2),它同時也是一個三角數(即 n(n+1)/2)。
這個問題其實就蠻古老的,例如有名的阿基米德分牛問題,也有類似的要求。解法的關鍵是,一個正整數 m 若是三角數,則 8m+1 會是一個平方數,反之亦然。所以,因為 x^2 是一個三角數,所以 8x^2 + 1 會是一個平方數,設它為 y^2,這樣會得到一個 Pell's equation:
y^2 - 8x^2 = 1
解 Pell's equation 的確是會用到連分數,這個例子中會需要用到 sqrt(8) 的連分數。不過這個式子倒是有個很明顯的解,就是 y = 3, x = 1。
要求出更多的解,除了用連分數之外,也可以用下面的方法:
y^2 - 8x^2 = (y + sqrt(8) x) (y - sqrt(8) x) = 1
因此
(y + sqrt(8) x)^n (y - sqrt(8) x)^n = 1
n 是任意正整數。也就是說,假設已經有一組解(例如 y = 3, x = 1),就可以很容易計算出更多的解。比如說:
(3 + sqrt(8))^2 = 17 + 6 sqrt(8)
所以 y = 17, x = 6 也是一組解。
現在有了 x,就需要算出 n,因為題目要求 n 是 50 ~ 500 之間。算出 n 就容易多了:因為
n(n+1)/2 = x^2
-> n^2 + n = 2x^2
所以要算出 n,只需要把 x 乘上 sqrt(2),再取整數部份即可(因為 n^2 < 2x^2 且 (n+1)^2 > 2x^2)。所以,x = 6 的時候 n = 8。很容易驗證這個答案是正確的(1 + 2 + ... + 5 = 15,7 + 8 = 15)。另外也可以注意到因為 y^2 = 8x^2 + 1,所以
y^2 - 1 = 8x^2
-> (y + 1) (y - 1) / 4 = 2x^2
-> (y + 1) / 2 * (y - 1) / 2 = 2x^2
所以如果 n = (y - 1) / 2 則 n (n + 1) = 2x^2,也就是要求得的 n。
要計算出 50 ~ 500 之間的 n,需要再找更大的 x:
(3 + sqrt(8))^3 = 99 + 35 sqrt(8) -> x = 35, n = 49
(3 + sqrt(8))^4 = 577 + 204 sqrt(8) -> x = 204, n = 288
這就是原問題的解了。
假設你在一條街道上,有 n 間房子,路牌號碼是 1 ~ n。其中有一間房子(號碼 x),它的左邊所有房子的路牌號碼總和,和它右邊的房子的路牌號碼總和相同。如果 n 在 50 至 500 之間,那麼 n 和 x 各是多少?
文章中提到 Ramanujan 很快就利用連分數解出了這個問題,讓他的室友 Mahalanobis 非常驚訝。
當然,Ramanujan 是數學天才。不過這個問題讓我覺得很有意思:它看起來算是相當簡單,我想可能小學生也能聽懂。不過這個問題倒底要怎麼解呢?
考慮 x 左邊的房子,即號碼 1 ~ x-1 的房子,其路牌號碼總和就是 x(x-1)/2。它右邊的房子,路牌號碼總和是 n(n+1)/2 - x(x+1)/2。這兩個數字要一樣,所以:
x(x-1)/2 = n(n+1)/2 - x(x+1)/2
-> x^2 = n(n+1)/2
所以,問題變成,要找出一個平方數(即 x^2),它同時也是一個三角數(即 n(n+1)/2)。
這個問題其實就蠻古老的,例如有名的阿基米德分牛問題,也有類似的要求。解法的關鍵是,一個正整數 m 若是三角數,則 8m+1 會是一個平方數,反之亦然。所以,因為 x^2 是一個三角數,所以 8x^2 + 1 會是一個平方數,設它為 y^2,這樣會得到一個 Pell's equation:
y^2 - 8x^2 = 1
解 Pell's equation 的確是會用到連分數,這個例子中會需要用到 sqrt(8) 的連分數。不過這個式子倒是有個很明顯的解,就是 y = 3, x = 1。
要求出更多的解,除了用連分數之外,也可以用下面的方法:
y^2 - 8x^2 = (y + sqrt(8) x) (y - sqrt(8) x) = 1
因此
(y + sqrt(8) x)^n (y - sqrt(8) x)^n = 1
n 是任意正整數。也就是說,假設已經有一組解(例如 y = 3, x = 1),就可以很容易計算出更多的解。比如說:
(3 + sqrt(8))^2 = 17 + 6 sqrt(8)
所以 y = 17, x = 6 也是一組解。
現在有了 x,就需要算出 n,因為題目要求 n 是 50 ~ 500 之間。算出 n 就容易多了:因為
n(n+1)/2 = x^2
-> n^2 + n = 2x^2
所以要算出 n,只需要把 x 乘上 sqrt(2),再取整數部份即可(因為 n^2 < 2x^2 且 (n+1)^2 > 2x^2)。所以,x = 6 的時候 n = 8。很容易驗證這個答案是正確的(1 + 2 + ... + 5 = 15,7 + 8 = 15)。另外也可以注意到因為 y^2 = 8x^2 + 1,所以
y^2 - 1 = 8x^2
-> (y + 1) (y - 1) / 4 = 2x^2
-> (y + 1) / 2 * (y - 1) / 2 = 2x^2
所以如果 n = (y - 1) / 2 則 n (n + 1) = 2x^2,也就是要求得的 n。
要計算出 50 ~ 500 之間的 n,需要再找更大的 x:
(3 + sqrt(8))^3 = 99 + 35 sqrt(8) -> x = 35, n = 49
(3 + sqrt(8))^4 = 577 + 204 sqrt(8) -> x = 204, n = 288
這就是原問題的解了。
2007年6月27日 星期三
最新的 TOP500
最新的 TOP500 列表又發表了。BlueGene/L 仍然穩居第一名,而且還有兩部新的 BlueGene 電腦進入了前十名。現在前八名的電腦都是位於美國的電腦。另外,前三名的電腦都超過了 100 TFLOPS。
前十名中另一部新電腦是 Dell 的 cluster,位於第八名。第十名的電腦也是一部新電腦,是 SGI 的 Altix 系統。
現在日本最快的電腦是一部 NEC 建置的 Sun Fire X4600 cluster,使用 Opteron 處理器和 Clearspeed 加速器,位於第十四名。
前十名中另一部新電腦是 Dell 的 cluster,位於第八名。第十名的電腦也是一部新電腦,是 SGI 的 Altix 系統。
現在日本最快的電腦是一部 NEC 建置的 Sun Fire X4600 cluster,使用 Opteron 處理器和 Clearspeed 加速器,位於第十四名。
訂閱:
文章 (Atom)