對基于數(shù)據(jù)分集的多線程程序設(shè)計(jì)玷室，OpenMP是一個(gè)很好的選擇俏扩。同時(shí)花颗，使用OpenMP也提供了更強(qiáng)的靈活性，可以較容易的適應(yīng)不同的并行系統(tǒng)配置西傀。線程粒度和負(fù)載平衡等是傳統(tǒng)多線程程序設(shè)計(jì)中的難題斤寇，但在OpenMp中桶癣，OpenMp庫從程序員手中接管了部分這兩方面的工作拥褂。但是，作為高層抽象牙寞，OpenMp并不適合需要復(fù)雜的線程間同步和互斥的場合饺鹃。
OpenMp的另一個(gè)缺點(diǎn)是不能在非共享內(nèi)存系統(tǒng)（如計(jì)算機(jī)集群）上使用，一般在這樣的系統(tǒng)上间雀，MPI使用較多悔详。
在Visual Studio中使用OpenMP其實(shí)很簡單，只要將 Project 的Properties中C/C++里L(fēng)anguage的OpenMP Support開啟（參數(shù)為 /openmp）惹挟，就可以讓VC++在編譯時(shí)就可以支持OpenMP 的語法了茄螃。而在編寫使用OpenMP 的程序時(shí)，添加#include <omp.h>即可连锯。下面是一個(gè)實(shí)例：
并行計(jì)算復(fù)習(xí)————第二篇 并行計(jì)算理論基礎(chǔ)：并行算法設(shè)計(jì)
PRAM（Parallel Random Access Machine）并行隨機(jī)存取機(jī)器归苍，是一種抽象并行計(jì)算模型，它假設(shè)：
3.BSP模型（MIMD-DM）
BSP（Bulk Synchronous Parallel）大同步并行機(jī)（APRAM算作輕量）是一個(gè)分布式存儲的MIMD模型运怖，它的計(jì)算由若干全局同步分開的拼弃、周期為L的超級步組成，各超級步中處理器做LM操作并通過選路器接收和發(fā)送消息摇展；然后做一次全局檢查吻氧，以確定該超級步是否已經(jīng)完成（塊內(nèi)異步并行，塊間顯式同步）
參數(shù)：處理器數(shù)p咏连、選路器吞吐率g盯孙、全局同步間隔L、一個(gè)超級步中一個(gè)處理器至多發(fā)送或接收h條消息
4.LogP模型：MIMD-DM祟滴，點(diǎn)到點(diǎn)通訊
LogP模型是分布式存儲振惰、點(diǎn)到點(diǎn)通信的MIMD模型
LogP采取隱式同步，而不顯式同步障
Ch6 并行算法基本設(shè)計(jì)策略
6.1 串改并
6.2 全新設(shè)計(jì)
6.2 借用法
Ch7 并行算法常用設(shè)計(jì)技術(shù)
6.1 劃分設(shè)計(jì)技術(shù)
程序中的時(shí)間復(fù)雜度是怎么計(jì)算的踱启？
一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間报账，從理論上是不能算出來的研底，必須上機(jī)運(yùn)行測試才能知道。但我們不可能也沒有必要對每個(gè)算法都上機(jī)測試透罢，只需知道哪個(gè)算法花費(fèi)的時(shí)間多榜晦，哪個(gè)算法花費(fèi)的時(shí)間少就可以了。并且一個(gè)算法花費(fèi)的時(shí)間與算法中語句的執(zhí)行次數(shù)成正比例羽圃，哪個(gè)算法中語句執(zhí)行次數(shù)多乾胶，它花費(fèi)時(shí)間就多。一個(gè)算法中的語句執(zhí)行次數(shù)稱為語句頻度或時(shí)間頻度朽寞。記為T(n)识窿。
計(jì)算方法
- 一般情況下，算法的基本操作重復(fù)執(zhí)行的次數(shù)是模塊n的某一個(gè)函數(shù)f（n）脑融，因此喻频，算法的時(shí)間復(fù)雜度記做：T（n）=O（f（n））
分析：隨著模塊n的增大，算法執(zhí)行的時(shí)間的增長率和f（n）的增長率成正比肘迎，所以f（n）越小甥温，算法的時(shí)間復(fù)雜度越低，算法的效率越高妓布。 - 在計(jì)算時(shí)間復(fù)雜度的時(shí)候姻蚓，先找出算法的基本操作，然后根據(jù)相應(yīng)的各語句確定它的執(zhí)行次數(shù)匣沼，再找出T（n）的同數(shù)量級（它的同數(shù)量級有以下：1狰挡，Log2n ，n 释涛，nLog2n 加叁，n的平方，n的三次方枢贿，2的n次方殉农，n！）局荚，找出后超凳，f（n）=該數(shù)量級，若T(n)/f(n)求極限可得到一常數(shù)c耀态，則時(shí)間復(fù)雜度T（n）=O（f（n））
例：算法：
for（i=1;i<=n;++i）
{
for(j=1;j<=n;++j)
{
c[ i ][ j ]=0; //該步驟屬于基本操作 轮傍，執(zhí)行次數(shù)：n的平方 次
for(k=1;k<=n;++k){
c[ i ][ j ]+=a[ i ][ k ]*b[ k ][ j ]; //該步驟屬于基本操作 ，執(zhí)行次數(shù)：n的三次方 次
}
}
則有 T（n）= n的平方+n的三次方首装，根據(jù)上面括號里的同數(shù)量級创夜，我們可以確定 n的三次方 為T（n）的同數(shù)量級
則有f（n）= n的三次方，然后根據(jù)T（n）/f（n）求極限可得到常數(shù)c
則該算法的 時(shí)間復(fù)雜度：T（n）=O（n^3） 注：n^3即是n的3次方仙逻。
2.1. 分類
按數(shù)量級遞增排列驰吓，常見的時(shí)間復(fù)雜度有：
常數(shù)階O(1),對數(shù)階O(log2n),線性階O(n),
線性對數(shù)階O(nlog2n),平方階O(n2)涧尿，立方階O(n3),...，
k次方階O(n^k), 指數(shù)階O(2^n) 檬贰。隨著問題規(guī)模n的不斷增大姑廉，上述時(shí)間復(fù)雜度不斷增大，算法的執(zhí)行效率越低翁涤。
關(guān)于對其的理解[《數(shù)據(jù)結(jié)構(gòu)（C語言版）》]------[嚴(yán)蔚敏][吳偉民]編著 第15頁有句話"整個(gè)算法的執(zhí)行時(shí)間與基本操作重復(fù)執(zhí)行的次數(shù)成正比桥言。"基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)f(n)，于是算法的時(shí)間量度可以記為：T(n) = O( f(n) )如果按照這么推斷葵礼，T(n)應(yīng)該表示的是算法的時(shí)間量度号阿，也就是算法執(zhí)行的時(shí)間。而該頁對“語句頻度”也有定義：指的是該語句重復(fù)執(zhí)行的次數(shù)鸳粉。如果是基本操作所在語句重復(fù)執(zhí)行的次數(shù)扔涧，那么就該是f(n)。上邊的n都表示的問題規(guī)模赁严。
一般來說扰柠，時(shí)間復(fù)雜度是總運(yùn)算次數(shù)表達(dá)式中受n的變化影響最大的那一項(xiàng)(不含系數(shù))
比如：一般總運(yùn)算次數(shù)表達(dá)式類似于這樣：
a2^n+bn3+c*n2+dnlg(n)+en+f
a<>0時(shí)，時(shí)間復(fù)雜度就是O(2^n);
a=0,b<>0 =>O(n^3);
a,b=0,c<>0 =>O(n^2)依此類推
那么疼约，總運(yùn)算次數(shù)又是如何計(jì)算出的呢？一般來說蝙泼，我們經(jīng)常使用for循環(huán)程剥，就像剛才五個(gè)題，我們就以它們?yōu)槔?.循環(huán)了nn次汤踏，當(dāng)然是O(n2)2.循環(huán)了(n+n-1+n-2+...+1)≈(n2)/2织鲸，因?yàn)闀r(shí)間復(fù)雜度是不考慮系數(shù)的，所以也是O(n2)3.循環(huán)了(1+2+3+...+n)≈(n2)/2,當(dāng)然也是O(n2)4.循環(huán)了n-1≈n次溪胶，所以是O(n)5.循環(huán)了(12+22+32+...+n2)=n(n+1)(2n+1)/6(這個(gè)公式要記住哦)≈(n3)/3搂擦，不考慮系數(shù)，自然是O(n^3)另外哗脖，在時(shí)間復(fù)雜度中瀑踢，log(2,n)(以2為底)與lg(n)(以10為底)是等價(jià)的，因?yàn)閷?shù)換底公式：log(a,b)=log(c,b)/log(c,a)所以才避，log(2,n)=log(2,10)*lg(n),忽略掉系數(shù)橱夭，二者當(dāng)然是等價(jià)的
