Discussion:
[請益] 那些語言或程式用上 多核心 CPU
(时间太久无法回复)
ggg
2007-05-08 00:11:08 UTC
Permalink
Notebook 都改用雙核心 cpu , 那些程式或應用是已經用上這項技術的 ?
要發揮多核心的作用, 使用那種程式語言會比較適當 ?

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.115.5.55
璉璉
2007-05-08 01:44:31 UTC
Permalink
WinNT (NT/2k/XP/2003/Vista) 系列,雙顆 CPU 以上,會保留一顆系統用,另一顆程式用。
所以只有雙核,你的程式只能用到 1/2 那一半而已。

四核的以上可能才有價值看一看相關的技術吧~
微軟有支援 Open MPI 的樣子,印象中是要另外下載函式庫...

先前台灣微軟網頁有,後來我找不到。

在介紹 Win2003 的 計算叢集伺服器裡面寫的,簡稱叫 CCS 。
於 news:4U11bh%248vY%40ptt.cc 發表
Notebook 都改用雙核心 cpu , 那些程式或應用是已經用上這項技術的 ?
要發揮多核心的作用, 使用那種程式語言會比較適當 ?
--
風禹科技驗證有限公司 ASP.NET Web News Reader 0.2.6 UTF-8 Beta
網站地圖 http://tlcheng.twbbs.org/wwwmap.htm
流域防洪/區域水資源/徐昇網/玫瑰圖/語音通訊 文章與程式
Basic/Fortran/Windows API/.Net/輔助說明檔 原始碼、文章與討論
微軟程式設計、系統管理使用新技術論壇討論區,網友回覆後即時簡訊、電子郵件通知:
MSDN: http://forums.microsoft.com/msdn-cht/default.aspx?siteid=14
TechNet: http://forums.microsoft.com/technet-cht/default.aspx?siteid=23
--
ASPNET News Reader http://tlcheng.twbbs.org/News/Reader.aspx
RSS 2.0 http://tlcheng.twbbs.org/News/rss2.aspx?Action=List&Newsgroup=tw.bbs.comp.language
ggg
2007-05-08 03:43:15 UTC
Permalink
※ 引述《***@bala.mis.ccu.edu.tw (keep healthy body)》之銘言:
: ※ 引述《***@ptt.cc (ggg)》之銘言:
: > Notebook 都改用雙核心 cpu , 那些程式或應用是已經用上這項技術的 ?
: > 要發揮多核心的作用, 使用那種程式語言會比較適當 ?
: 其實支援雙核心第一應該是程式語言所跑的平台
: 也就是說假設你的OS根本就不支援雙核心
: 你用什麼程式語言應該都一樣
OS 應該也是用程式語言寫出來的, X86 server 不是也有多處理機的 ?
記得 Linux 跟 MicroSoft OS 都支援多處理機, 多核心不就能像
multi-cpu 那樣跑, 好像 Intel 單主機板能裝到 4-6 cpu ?

: 當OS有支援的狀況下
: 再來使用某程式語言開發的時候,或多或少到run time的時候
: OS應該會決定是否要使用到雙核心的技術
: 我是覺得這一段應該是OS會做掉
: 也就是說哪種程式語言可能都一樣
: 或許有某個程式語言有所謂的支援雙核心
: 但我想,那大概也只是讓你在開發的過程當中選擇是否要應用到雙核心技術
程式都是片段片段的寫出來, 好幾個程式不也是可以同時下命令點選一起跑, 這
樣的跑法只有寫 OS 的程式語言才會有嗎 ? 是因為程式語言的關係嗎 ?

: 記得看過一篇文章是說當時INTEL為了開發雙核心的技術
: 光compiler就搞了好幾年,因為當換算到machine time的時候要決定哪段code
: 要讓哪個CPU跑,還要解決同步不同步問題
compiler 要負責計算 machine time ? 現在的 compiler 會回答說這個程式編好
後, 大概跑多久會做完 ?

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.115.5.55
我想把整片天空打開
2007-05-08 04:15:10 UTC
Permalink
intel 有出個 threading package 叫 Intel Threading Building Blocks.
可以參考一下.
http://www.intel.com/cd/software/products/asmo-na/eng/294797.htm

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.123.19.235
ggg
2007-05-08 11:46:52 UTC
Permalink
※ 引述《avhacker (我想把整片天空打開)》之銘言:
: intel 有出個 threading package 叫 Intel Threading Building Blocks.
: 可以參考一下.
: http://www.intel.com/cd/software/products/asmo-na/eng/294797.htm
謝謝指點.
不曉得這種 thread 跟一般的 thread 有那些不一樣的地方 ?

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.115.5.55
李知秋
2007-05-09 02:36:05 UTC
Permalink
你想問的是:

Multi-Core Programming

請以此關鍵字上 Google 查,Intel 有出 package。

多核心的程式,要有該硬體的 package 支援才行。

--
〒作者:zsexdrcf 來自:ipvr4.csie.ncu.edu.tw
◎二進位的世界【140.115.50.50‧bbs.ncu.cc】
unknown
2007-05-14 13:49:07 UTC
Permalink
刪光光...
: OS 應該也是用程式語言寫出來的, X86 server 不是也有多處理機的 ?
: 記得 Linux 跟 MicroSoft OS 都支援多處理機, 多核心不就能像
: multi-cpu 那樣跑, 好像 Intel 單主機板能裝到 4-6 cpu ?

多工應用必須要有作業系統與硬體互相搭配,雖然作業系統用也是用語言寫出來的,不過
在牽涉與CPU相關的各項作業時,就必須用到CPU提供的指令集。也就是說,作業系統因為
有CPU的硬體支援,及自己實作的各項功能,而提供了其下之應用程式的多工需求。

: 程式都是片段片段的寫出來, 好幾個程式不也是可以同時下命令點選一起跑, 這
: 樣的跑法只有寫 OS 的程式語言才會有嗎 ? 是因為程式語言的關係嗎 ?
你所謂的「好幾個程式不也是可以同時下命令點選一起跑」是Win32
實做Multi-processing的結果,只是多工技術的一種,你要不要先去找本書看看啊?
感覺你對多工還是不瞭解。

: compiler 要負責計算 machine time ? 現在的 compiler 會回答說這個程式編好
: 後, 大概跑多久會做完 ?
這段非常怪,Compiler也許可以回答你每個指令要花多少週期做完,但無法回答你這程式
要花多少時間才能跑完,事實上,只要是圖靈機(Turing Machine,目前的機器皆是),
是無法回答這個問題的,因為這是所謂的Halting Problem.

--

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.125.254.86
點點加油
2007-05-14 17:45:53 UTC
Permalink
: 現在的 Windows , Linux OS 不是多處理機又是多工的嗎 ? 那麼多核心為甚麼
: 不能像多處理機那樣跑 ?
多工,是單核心,做得很快讓你覺得是同時在做,達到mutiprocess的效果

__A__
___B__
__C__

..


: OS 也是用程式語言寫出來的, 現在的程式語言寫不出有多工的程式嗎 ?
多工的程式?嗯…用詞不太對 建議您可以認真的瞭解一下多工的定義
那些看似同時可做兩件事的其實都是很快的context switch 也就是multiprogramming

: 那麼使用 thread lib 寫的程式不算多工 ?
同前面 多工是以kernel執行的架構來決定 若同一process下的不同thread可在不同CPU
上執行 那它可能就像是你想的thread lib做出來的 若這樣那就叫parallel了


: : 你所謂的「好幾個程式不也是可以同時下命令點選一起跑」是Win32
: : 實做Multi-processing的結果,只是多工技術的一種,你要不要先去找本書看看啊?
: : 感覺你對多工還是不瞭解。
: 寫 OS 的程式語言跟寫一般程式的程式語言沒有不同吧 ?
: 既然 OS 是多工的, 程式就是透過 OS 平台在其上跑的, 那多個片段程式
: 一起跑不就是多工 ? 再把多個片段程式合在一起, 讓多核心對每段同時
^^^^^^^^^^^^^^^^^ 是! 可是這不叫「程式多工」,是OS達成「多工」
: 跑, 那不就是多核心一起跑 ? 如果說不可以, 那又差在那裡 ?
不可以 parallel的系統需要communication 也就是當你形容的多個CPU平行執行多個程式
時,它是需要溝通的,這些溝通的overhead使得parallel非常難做 也就是為什麼intel
要搞這麼久
還有 多核心(CPU)的電腦執行效率並非1+1=2 事實上1+1約等於1.2左右(有錯請鞭)
不過這個是可以克服的 也是目前努力的方向
: : 這段非常怪,Compiler也許可以回答你每個指令要花多少週期做完,但無法回答你這程式
: : 要花多少時間才能跑完,事實上,只要是圖靈機(Turing Machine,目前的機器皆是),
: : 是無法回答這個問題的,因為這是所謂的Halting Problem.
: 那就要問 avi 兄台這段話的意思:
: " 記得看過一篇文章是說當時INTEL為了開發雙核心的技術
: 光compiler就搞了好幾年,因為當換算到machine time的時候要決定哪段code
: 要讓哪個CPU跑,還要解決同步不同步問題"

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.162.100.42
SoMiMi FaReRe
2007-05-15 08:00:17 UTC
Permalink
※ 引述《***@bbs.cs.nctu.edu.tw (@++@)》之銘言:
: 不對吧
: halting problem是"無法判斷會不會`停'"
: 跟要花多少時間沒關係
: 教科書上有明確的定義喔
: wikipedia也查的到
判斷程式花多少時間 這個問題基本上比 Halting Problem還要困難
正式上來說 Halting Problem可被 reduce to (判斷程式花多少時間).
因此如果compiler可以判斷程式要花多少時間 就等於解了halting problem.
但已知 Halting Problem在Turing Machine上是undecidable
所以(判斷程式花多少時間)也是 undecidable.

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 132.239.55.127
XOO
2007-05-15 09:25:44 UTC
Permalink
※ 引述《somi (SoMiMi FaReRe)》之銘言:
: ※ 引述《***@bbs.cs.nctu.edu.tw (@++@)》之銘言:
: : 不對吧
: : halting problem是"無法判斷會不會`停'"
: : 跟要花多少時間沒關係
: : 教科書上有明確的定義喔
: : wikipedia也查的到
: 判斷程式花多少時間 這個問題基本上比 Halting Problem還要困難
: 正式上來說 Halting Problem可被 reduce to (判斷程式花多少時間).
: 因此如果compiler可以判斷程式要花多少時間 就等於解了halting problem.
: 但已知 Halting Problem在Turing Machine上是undecidable
: 所以(判斷程式花多少時間)也是 undecidable.
如果程式 N 不會停的話,判斷程式 M 也跟著不停住,那其實也對。
像是在 Unix 下 time 指令,不就會丟給你程式 M 的執行時間呢 XD

當然"判斷多少花多少時間",絕對是 undecidable 的,
我只是想說,問題是 undecidable 不代表寫不出程式啊 ...

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 125.229.165.234
推 rightson:XD  140.113.239.71 05/15 17:25
ggg
2007-05-19 04:00:35 UTC
Permalink
※ 引述《***@bbs.cs.nctu.edu.tw (@++@)》之銘言:
: ※ 引述《***@ptt.cc (SoMiMi FaReRe)》之銘言:
: > 判斷程式花多少時間 這個問題基本上比 Halting Problem還要困難
: > 正式上來說 Halting Problem可被 reduce to (判斷程式花多少時間).
: > 因此如果compiler可以判斷程式要花多少時間 就等於解了halting problem.
: > 但已知 Halting Problem在Turing Machine上是undecidable
: > 所以(判斷程式花多少時間)也是 undecidable.
: 感謝補充
: 其實原po沒有講"錯"
: 只是敘述方式讓我覺得他重新定義了halting problem
: =======
: 這段非常怪,Compiler也許可以回答你每個指令要花多少週期做完,但無法回答你這程式
: 要花多少時間才能跑完,事實上,只要是圖靈機(Turing Machine,目前的機器皆是),
: 是無法回答這個問題的,因為這是所謂的Halting Problem.
===
多重程式, 多工, 多處理機, 平行計算, 多核心等等, 針對特定 AP 是可以讓
Compiler 來分析一個程式, 找出前後次序無關與相關的片段. 假設前後 A,B
兩片斷是相關的, 兩個 CPU 或 核心 C1, C2 被派來做這兩個片段, 因為 C2
要等 C1 做完 A, 才可以接續著做 B, 如果 C2 知道 C1 大概需做多久時間 T,
就可以離開一段時間 T 再回來檢查 C1 做完沒. 如果是這樣, 片段 A 讓 C1
做是可以事先依 A 的程式指令類別與數量估出所需 Cycle 數, 再依 C1 的
Clock 速率預估出所需時間, 就能決定大概該等多久. 只估片段而不涉及整個
大程式最終會不會(或該不該)停, 那還是可以估算的.

1.現在的 Compiler 似乎不做較長片段執行時間的估算. 但還是可以估, 未必
準確就是.

2.時延等候讓 cpu 或 core 去做別的事或都不做事, 就不必不停叫 CPU 去檢
試, 造成對 instruction pipeline 或 cache 的干擾, 固然是一種方法, 但
也不是很困難做不到的問題, 至少, 不會升級到 Halting Problem .

假如是這種狀況, 似乎事情還不是那麼難纏 ! 不過, Intel 因此被 AMD 拼過去,
那一定還有更大條的才是.


--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.115.6.234
ephesians
2007-05-19 12:05:22 UTC
Permalink
※ 引述《ggg12345 (ggg)》之銘言:
: 1.現在的 Compiler 似乎不做較長片段執行時間的估算. 但還是可以估, 未必
: 準確就是.
: 2.時延等候讓 cpu 或 core 去做別的事或都不做事, 就不必不停叫 CPU 去檢
: 試, 造成對 instruction pipeline 或 cache 的干擾, 固然是一種方法, 但
: 也不是很困難做不到的問題, 至少, 不會升級到 Halting Problem .
: 假如是這種狀況, 似乎事情還不是那麼難纏 ! 不過, Intel 因此被 AMD 拼過去,
: 那一定還有更大條的才是.

很抱歉,開始看不懂你在講什麼了.
有哪個compiler會做程式執行時間的估算嗎? 好厲害喔...
意思是如果我寫這樣的程式:

void f() { f(); }

int main() { f(); return 0; }

此程式compiled之後, compiler會告訴我
"The program takes infinite time to execute." 你的意思是這樣子嗎?


學過一些compiler設計的書,沒在講程式執行時間評估.



--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.160.114.183
ggg
2007-05-19 12:57:35 UTC
Permalink
作者: ggg12345 (ggg) 站內: Programming
標題: Re: [請益] 那些語言或程式用上 多核心 CPU
時間: Sat May 19 20:54:34 2007

※ 引述《ephesians (ephesians)》之銘言:
: ※ 引述《ggg12345 (ggg)》之銘言:
: : 1.現在的 Compiler 似乎不做較長片段執行時間的估算. 但還是可以估, 未必
: : 準確就是.
: : 2.時延等候讓 cpu 或 core 去做別的事或都不做事, 就不必不停叫 CPU 去檢
: : 試, 造成對 instruction pipeline 或 cache 的干擾, 固然是一種方法, 但
: : 也不是很困難做不到的問題, 至少, 不會升級到 Halting Problem .
: : 假如是這種狀況, 似乎事情還不是那麼難纏 ! 不過, Intel 因此被 AMD 拼過去,
: : 那一定還有更大條的才是.
: 很抱歉,開始看不懂你在講什麼了.
: 有哪個compiler會做程式執行時間的估算嗎? 好厲害喔...
: 意思是如果我寫這樣的程式:
: void f() { f(); }
: int main() { f(); return 0; }
: 此程式compiled之後, compiler會告訴我
: "The program takes infinite time to execute." 你的意思是這樣子嗎?
: 學過一些compiler設計的書,沒在講程式執行時間評估.
===================================================================
那您先得看底下這一段: 這是 avi 先進提供的.
前面已有人質疑是 Halting Problem 能解嗎 ? 但應該不是這樣的對象與用途.

多核心 如同 多處理機, 碰上互斥的 critical section (region) 要等待時,
如何個等法是個問題. critical section 是一種假設在 finite time 必得執
行完的程式片段及相關資料(或資源), 能預估已進入 critcal section 執行
的 CPU 何時將釋出是有好處的.

compiler 在 code generation 階段估算 這種 critical section 片段程式
的 某類cpu cycle 數是沒有問題的.

譬如平行分區計算, 需得在交界處等候接手, 這種 pipeline 接續的算法在
finite element 法做計算時就用得上, 能估算就能解很多問題, 不必靠 os
提供派工與提供同步機制.

============================================================================
作者 ***@bala.mis.ccu.edu.tw (keep healthy body), 看板 programming
標題 Re: [請益] 那些語言或程式用上 多核心 CPU
Post by ggg
Notebook 都改用雙核心 cpu , 那些程式或應用是已經用上這項技術的 ?
要發揮多核心的作用, 使用那種程式語言會比較適當 ?
其實支援雙核心第一應該是程式語言所跑的平台
也就是說假設你的OS根本就不支援雙核心
你用什麼程式語言應該都一樣
當OS有支援的狀況下
再來使用某程式語言開發的時候,或多或少到run time的時候
OS應該會決定是否要使用到雙核心的技術
我是覺得這一段應該是OS會做掉
也就是說哪種程式語言可能都一樣
或許有某個程式語言有所謂的支援雙核心
但我想,那大概也只是讓你在開發的過程當中選擇是否要應用到雙核心技術

記得看過一篇文章是說當時INTEL為了開發雙核心的技術
光compiler就搞了好幾年,因為當換算到machine time的時候要決定哪段code
要讓哪個CPU跑,還要解決同步不同步問題
也因為這樣讓AMD的64位元搶得了進入市場的先機
anyway,我好像還是沒講到重點.....

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.115.6.234
D***@ptt.cc
2007-05-20 09:15:36 UTC
Permalink
※ 引述《xcycl (XOO)》之銘言:
: ※ 引述《somi (SoMiMi FaReRe)》之銘言:
: : 判斷程式花多少時間 這個問題基本上比 Halting Problem還要困難
: : 正式上來說 Halting Problem可被 reduce to (判斷程式花多少時間).
: : 因此如果compiler可以判斷程式要花多少時間 就等於解了halting problem.
: : 但已知 Halting Problem在Turing Machine上是undecidable
: : 所以(判斷程式花多少時間)也是 undecidable.
: 如果程式 N 不會停的話,判斷程式 M 也跟著不停住,那其實也對。
: 像是在 Unix 下 time 指令,不就會丟給你程式 M 的執行時間呢 XD
: 當然"判斷多少花多少時間",絕對是 undecidable 的,
: 我只是想說,問題是 undecidable 不代表寫不出程式啊 ...
一個問題是undecidable就是說不存在程式可以decide這個問題
既然不存在到底是要怎麼寫?

--

如果真的寫出這種程式一定得Turing Award

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.209.144
ggg
2007-05-20 11:41:46 UTC
Permalink
※ 引述《DreamLinuxer ( )》之銘言:
: ※ 引述《xcycl (XOO)》之銘言:
: : 如果程式 N 不會停的話,判斷程式 M 也跟著不停住,那其實也對。
: : 像是在 Unix 下 time 指令,不就會丟給你程式 M 的執行時間呢 XD
: : 當然"判斷多少花多少時間",絕對是 undecidable 的,
: : 我只是想說,問題是 undecidable 不代表寫不出程式啊 ...
: 一個問題是undecidable就是說不存在程式可以decide這個問題
: 既然不存在到底是要怎麼寫?
====================================================================
粗略的說 Halting Problem , 就是說不存在一種算法或程式, 可以針對所有的
程式, 透過計算判斷, 判定最終是否會停還是不會停.

沒有這種如此本事高強的程式或算法, 並不表示本事差一點的算法或程式就不
存在, 闢如一個程式都沒 if loop , 開始到結束只有算術計算的 assignment
statement(除了分母=0 例外) , 那是能判斷計算時間也能知道何時會結束的.

就像 compiler 不會知道程式解題解對了沒有, 但 Compiler 知道語法寫錯是
翻譯不出對的指令, 但也能替你的程式做些假設的狀況強行翻譯, 看起來好像
真的能自動除錯, 但也不保證就猜對.


--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.115.5.62
XOO
2007-05-20 17:28:10 UTC
Permalink
※ 引述《DreamLinuxer ( )》之銘言:
: ※ 引述《xcycl (XOO)》之銘言:
: : 如果程式 N 不會停的話,判斷程式 M 也跟著不停住,那其實也對。
: : 像是在 Unix 下 time 指令,不就會丟給你程式 M 的執行時間呢 XD
: : 當然"判斷多少花多少時間",絕對是 undecidable 的,
: : 我只是想說,問題是 undecidable 不代表寫不出程式啊 ...
: 一個問題是undecidable就是說不存在程式可以decide這個問題
: 既然不存在到底是要怎麼寫?
Well, 我講嚴謹一點,
Turing-recognizable 是嚴格包含 Turing-decidable 語言的。

而 language 是 recogizable 但不是 decidable 的,
意指存在 Turing Machine 能夠 recognize 這問題,只是不見得
任意的 input 一定會 halt。講成白話,意思就是程式寫得出來,
只是不見得會停而已。

所以能不能 decide 跟寫不寫得出程式無關。
--
Sipser 寫的計算理論還滿淺顯的, 可以看一下搞清楚兩者的區別。

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.116.142.221
XOO
2007-05-21 14:19:22 UTC
Permalink
※ 引述《***@bbs.cs.nctu.edu.tw (小強)》之銘言:
: ※ 引述《***@ptt.cc (XOO)》之銘言:
: > Well, 我講嚴謹一點,
: > Turing-recognizable 是嚴格包含 Turing-decidable 語言的。
: > 而 language 是 recogizable 但不是 decidable 的,
: > 意指存在 Turing Machine 能夠 recognize 這問題,只是不見得
: > 任意的 input 一定會 halt。講成白話,意思就是程式寫得出來,
: > 只是不見得會停而已。
: > 所以能不能 decide 跟寫不寫得出程式無關。
: 好吧
: 那請您告訴我這個簡單的procedure到底會不會停?
: 在下資質駑鈍真的想不出來
: while (true) {
: int x = get random number from 0 to 100000
: if (x == 10) break;
: }
必須明確定義, 何謂 "get a random number"
一般程式語言內建的函式是 pseudo-random generator 並不是真正 "random",
當然,就如同之前有人回的,一般亂數產生器跑夠多次之後,會取到 10 而會停住。

n
若是一機率分配函數 p:{1, ..., 100000} → [0, 1], Σp(i) = 1
i=1
那就只是機率問題。但就算 p(10) 的機率不等於 0 ,
也只能說該 procedure 是 almost surely 會停的,但不能"確定"會停,
畢竟每次都取不到 10 的情況是存在,只是機率為零。

你可以看看 Probabilistic Turing Machine 的理論,
在 Wikipedia 或 計算理論和計算複雜度的教本都會提到 PTM 的理論模型。

如果你想藉此來闡述 "不存在程式可以判斷,其他程式是否會停" 這個觀念,
那你必須說明清楚,判斷是指任一輸入都可以在有限步驟內給出答案,也就是 decide。
但是這並不代表 "不存在程式可以 recognize,其他程式是否會停"。
在這裡說的 recognize, decide 請麻煩參考教本的定義,不要望文生義。

最後,幫你複習一下機率:事件一定發生的話,機率一定是 1;反之不成立,
用測度的語言來說,該事件跟樣本空間相差一個測度為零的集合。
因此,當某事件機率為 1 時,稱該事件 almost surely (中文不知道怎麼翻的)會發生。

題外話,在當代機率論公設(Kolmogorov提出的)底下,無法實作出能夠機會均等地,
隨機取出任一整數的方法。

almost surely: http://en.wikipedia.org/wiki/Almost_surely
PTM: http://en.wikipedia.org/wiki/Probabilistic_Turing_machine
TM: http://en.wikipedia.org/wiki/Deterministic_Turing_machine

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 125.229.165.204
ggg
2007-05-21 16:53:14 UTC
Permalink
※ 引述《***@bbs.cs.nctu.edu.tw (小強)》之銘言:
: ※ 引述《GOLDMEMBER (㊣阿多巴可安德爾 XD)》之銘言:
: > 一般compiler提供的簡單亂數產生器,原則上都要滿足值空間內任一值出現的機會相等
: > 這些就保證值空間內每一點在有限週期內都會輸出到
: > 你以下又沒有限制說拿到10要故意丟掉不准後面接,當然會停
: 老兄呀
: 我有說這個random number distribution必定是uniform的嗎?
: 你也別太急著跳進這個坑了
: 甚至我讓x是透過使用者輸入的一個數字
: 你能說這個程序確定會停嗎?
原來的 Halting Problem 是判斷任意一個程式 p 及其 input 最終是否會停 ?
程式 p 及 input 是已知的.


--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.115.5.62
ggg
2007-05-22 17:17:58 UTC
Permalink
※ 引述《ggg12345 (ggg)》之銘言:
: ※ 引述《avhacker (我想把整片天空打開)》之銘言:
: : intel 有出個 threading package 叫 Intel Threading Building Blocks.
: : 可以參考一下.
: : http://www.intel.com/cd/software/products/asmo-na/eng/294797.htm
: 謝謝指點.
: 不曉得這種 thread 跟一般的 thread 有那些不一樣的地方 ?

這裡有一個網頁是介紹這種 多核心 Simultaneous MultiThreading(SMT)
與 Hyperthred 的. 多核不是一個 chip 裡塞進多處理機, 而是有多個
Instruction Pointer , 各有對應的 interrupt fordwarding.

http://arstechnica.com/articles/paedia/cpu/hyperthreading.ars/1

Hyperthread 是由硬體支援的, 不必更動原來的 OS 架構, 因為 OS 都強調在
SMP 多處理機下照樣運作.

HyperThread 是一種硬體支援, 讓同一組 execution unit 藉助於部份是複製
且分開, 各自自備一套的 instruction queue , ip register 及 interrupt
handler . 就程式的執行言, 因為有多組 instruction pointer 使之看來像
有多組 logical processor, 饋入指令後, 指令的細部動作執行, 有一個硬體
的 sequence scheduler 來推動, 其主要作用是讓隨後共用的 multiple
pipeline function unit 儘量減少空檔, 雖然不是多處理機, 但各 thread
(或 process) 指令同時在不同的 pipeline function unit 同時執行, 就能
跑出像有多個 logical processor 同時在跑的計算效能.

這是從 instruction parallel 改為 thread parallel. 使得 OS 及 AP 可以
把多核心當成多處理機來用.

這種系統是同時用多核跑多個彼此性質不同的片段程式, 讓 multiple pipeline
function unit 都能同時利用上, 這應該不會觸及 halting problem 的疑問 !

就程式與程式語言來看, 多核 CPU 如何讓一個程式也能加以利用 ?

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.115.5.5
歐弟
2007-05-24 10:50:09 UTC
Permalink
即使在多核心的主機上,也不可能只跑一個AP

除非是相當計較運算時間的程式

不然多核心的排程部分就交給OS處理
--
☆ [Origin:椰林風情] [From: 61-62-48-70-adsl-tan.static] [Login: **] [Post: **]
ggg
2007-05-24 14:00:32 UTC
Permalink
這是[轉貼]的, 看來雙核心就是不同性質的程式, 多工的用法, 才可能用上
Multiple Pipeline Function Unit 的利用率.
=========================================================================

標 題: 關於雙核心﹕你不知道的五件事

我們知道﹐AMD和Intel都在鼓吹各自的雙核心技術﹐而業內人士也將2006看作
是“雙核”年。不過﹐在有關雙核的諸多新聞報道之下﹐隱藏著一些非同尋常的驚
人事實﹐而其中有些還不為我們所知﹐比如說以下5個有關雙核心的事實﹐你知道嗎﹖

1.Intel和AMD不是推出雙核心處理器的頭兩家公司

廣泛流傳的一種觀點是雙核心技術首先出現在PC領域﹐而AMD和Intel還在爭奪“第一”
的頭銜。但事實上﹐IBM才是多核心領域真正的始作俑者。該公司的第一款雙核心處
理器不是基於X86架構﹐而且是一款服務器CPU﹐即2001年推出並裝備在IBM RISC服務
器的雙核心Power4處理器。

2.雙核心的誕生是迫於技術挑戰﹐而不是一種超前技術

雙核心技術並不是Intel和AMD突然獲得的技術突破。實際上﹐處理器生產商更願意不
斷推出更快的單核心處理器﹐遺憾的是這並不可行﹐因為當運行頻率超過3GHz﹐單核
心處理器的功率開始突飛猛進。
比如﹐2005年Intel取消的4Ghz“Tejas”處理器功率就超過100W。

3.雙核心無需讓處理器運行頻率更高就能提高性能

我們知道現在無論是Intel還是AMD﹐其雙核心處理器的實際頻率都低於或者等同於其
最高端單核CPU的運行頻率。不過即使頻率稍低﹐雙核CPU的性能也將超過單核產品﹐
且二者的功率相當。
但由於兩個核心需要共享一些資源﹐因此雙核並無法令處理器性能倍增。AMD公司的
Lewis稱﹕“我們看到的是根據不同的應用﹐(雙核心處理器)性能獲得1.4-1.8倍的
提升。”
但許多技術媒體仍質疑雙核心的性能提升﹐Wikipedia就提到說“多核心處理器需要
操作系統的支持來優化第二計算資源的使用。”
簡單的說﹐多線程應用是雙核心處理器高性能的關鍵。過去幾年中在單核環境中我們
已經在推行多線程應用﹐而雙核技術來臨之後多線程更將被積極開發。“你們每天都
在運行一種強力的多線程應用軟件﹐它的名字叫操作系統”﹐Lewis這樣說道﹐“你
們一直擁有這樣一個多線程環境﹐而雙核心處理器讓這種環境運行得更加高效。”讓
我們期待Windows vista﹐這將是微軟首個在設計階段就將雙核心技術考慮在內的操
作系統。

4.幾乎半數PC用戶還對雙核心一竅不通

最近的一次調查表明﹐目前仍有48%的PC用戶不清楚什麼是雙核心處理器。當然在商業
市場情況就大有不同﹐數據中心經理和CIO們很清楚雙核心能帶給企業什麼好處。
Harris Interactive公司進行的這次調查主要集中於家庭用戶﹐42%的PC擁有者表示對
雙核心有點了解﹐另外的10%已經在使用雙核心處理器並聲稱對該技術非常了解。而在
這些對雙核技術或多或少有些了解的52%人群中﹐隻有12%在使用雙核心處理器系統。
當然﹐這個微小的比例將會逐漸提高﹐市調公司Frost & Sullivan預測雙核處理器將
以每年核技術或多或少有些了解的52%人群中﹐隻有12%在使用雙核心處理器系統。
當然﹐這個微小的比例將會逐漸提高﹐市調公司Frost & Sullivan預測雙核處理器將
以每年15-25%的比例取代單核產品﹐無論是在台式機、筆記本還是服務器市場。Intel
則有更大的目標──計劃在2006年出貨6000萬顆雙核心處理器。

5.雙核心不是尖端計算機技術的終點

幾年之內﹐雙核心就將成為過時的技術。Intel已經著手準備在2007年推出4核心服務
器處理器﹔AMD也正在研發4核心CPU。

而在更遠的未來﹐Intel還將推出代號Yorkfield的8核心產品﹐上市時間是2008年。
AMD也不甘示弱﹐表示將在2007年開始推出核心數量大於兩個的產品。而在非x86領
域﹐Sun已經準備推出裝備8核心CPU的UltraSparc T1(也就是之前的Niagara)服務
器。
沒錯﹐未來我們將用到越來越多的核心。Co-Design Automation Inc.的聯合創始人
Simon Davidmann說過的一句話很有道理﹕“一切處理器終都將成為多重處理器﹐而
我們必須學會使用它們。”

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.115.5.5
ggg
2007-05-28 04:47:53 UTC
Permalink
※ 引述《***@bbs.cs.nctu.edu.tw (小強)》之銘言:
: ※ 引述《***@ptt.cc (XOO)》之銘言:
: > Well, 我講嚴謹一點,
: > Turing-recognizable 是嚴格包含 Turing-decidable 語言的。
: > 而 language 是 recogizable 但不是 decidable 的,
: > 意指存在 Turing Machine 能夠 recognize 這問題,只是不見得
: > 任意的 input 一定會 halt。講成白話,意思就是程式寫得出來,
: > 只是不見得會停而已。
: > 所以能不能 decide 跟寫不寫得出程式無關。
: 好吧
: 那請您告訴我這個簡單的procedure到底會不會停?
: 在下資質駑鈍真的想不出來
: while (true) {
: int x = get random number from 0 to 100000
: if (x == 10) break;
: }
========================
Halting Problem 的證明通常都假設如果有這樣的程式(或 Machine)
存在, 就可據此做個反例(反命題), 然後再讓他對付自己(否逆命題),
最後證明不可能, 連帶的原命題也就不可能.
若對此有興趣, 那還是接 xen VM 會好玩一些, 因為 VM 可以使用
recursive VM , 就是把原 VM 整個程式當 input 餵給 VM 自己去跑,
看能否也一樣正常的模擬起來 ? 狀況非常像這個證明(其實不一樣, 只
有把自己當 input 餵給自己).
是否存在一個程式可以判定所有的程式會不會停下來(Halt) ?
是否存在一個程式可以模擬所有的程式所要展現的特性 ?

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.115.1.146

Loading...