串列程序並行化

Ⅰ c語言如何串列演算法並行化

你好，C的並行方法為擴展並行。即使用第三方C語擴展來實現，現在基於C的並行擴展有openMP、CUDA等，如果需要推薦書發消息給我。補充：你現在的想法跟AMD的差不多，但是實際用途只在部分代碼上有用，具體大的工程實踐還是需要相關人員自己進行並行設計，你可以通過很多書上的並行方法通過自己設計解析軟體把程序代碼分解為openMP代碼並作為預處理代碼。

Ⅱ 串列和並行的區別

串列和並行的區別為以下幾點：

1.數據傳送方式不同：串口傳輸方式為數據排成一行、一位一位送出接收也一樣,並口傳輸8位數據一次送出.

2.針腳不同：串口針腳少,並口針腳多.

3.用途不同：串口現在只用作控制介面,並口多用作列印機、掃描儀等介面.

4.並行數據傳輸是以計算機的字長，通常是8位、16位、32位為傳輸單位，一次傳送一個字長的數據。它適合於外部設備與CPU之間近距離信息交換。在相同頻率下,並口傳輸的效率是串口的幾倍。

5.串列傳輸即串列通信，是指使用一條數據線，將數據一位一位地依次傳輸，每一位數據占據一個固定的時間長度。其只需要少數幾條線就可以在系統間交換信息，特別適用於計算機與計算機、計算機與外設之間的遠距離通信。

拓展資料

串列是指數據一位一位地順序傳送，其特點是通信線路簡單，只要一對傳輸線就可以實現雙向通信（可以直接利用電話線作為傳輸線），從而大大降低了成本，特別適用於遠距離通信，但傳送速度早謹較慢。一條信息的各位數據被逐位按順序傳送的通訊方式稱為串列通訊。串列通訊的特點是：數據位的傳送，按位順序進行，最少只需一根傳輸線即可完成；成本低但傳送速度慢。串列通訊的距離可以從幾米到幾千米；根據信息的傳送方向，串列通襲散訊可以進一步分為單工、半雙工和全雙工三種。

並行是在操作系統中是指，一組程拍睜氏序按獨立非同步的速度執行，不等於時間上的重疊（同一個時刻發生)。要區別並發。並發是指：在同一個時間段內，兩個或多個程序執行，有時間上的重疊（宏觀上是同時，微觀上仍是順序執行）。並行也指8位數據同時通過並行線進行傳送，這樣數據傳送速度大大提高，但並行傳送的線路長度受到限制，因為長度增加，干擾就會增加，數據也就容易出錯。

Ⅲ 指令的串列執行和並行執行的區別

指令的串列執行和並行執行的區別為：過程不同、效率不同、資源利用率不同。

一、過程不同

1、串列執行：多道程序系統中多個程序（邏輯上互相獨立）或者一個程序中的多個程序段在執行的過程當中，一個程序執行沒結束前，另一個不能開始，要一個一個的執行。

2、並行執行：多道程序系統中多個程序（邏輯上互相獨立）或者一個程序中的多個程序段在執行的過程當中，一個程序執行沒結束，另一個已經開始。

二、效率不同

1、串列執行：串列執行的時間不重疊，執行效率低。

2、並行執行：並行執行的時間互相重疊，執行效率高。

三、資源利用率不同

1、串列執行：串列執行存在等待程序，資源利用率低。

2、並行執行：並行執行不存在等待程序，資源利用率高為。

Ⅳ 串列演算法並行化方法

先驗演算法一般是拿來做並行化的，先驗估計串列演算法下一部敗告消分需要的值，同時生成演算法每個察知步驟的結果友賣，如果預測失敗選擇回退

Ⅳ 單核cpu的並行過程，求解答

CPU並行編程概述
並行編程的演化
一個自然而然的問題是：為什麼要用並行編程？在20世紀70年代、80年代甚至90年代的一部分時間里，我們對單線程編程（或者稱為串列編程）非常滿意。你可以編寫一個程序來完成一項任務。執行結束後，它會給你一個結果。任務完成，每個人都會很開心！雖然任務已經完成，但是如果你正在做一個每秒需要數百萬甚至數十億次計算的粒子模擬，或者正在對具有成千上萬像素的圖像進行處理，你會希望程序運行得更快一些，這意味著你需要更快的CPU。

在2004年以前，CPU製造商IBM、英特爾和AMD都可以為你提供越來越快的處理器，處理器時鍾頻率從16 MHz、20 MHz、66 MHz、100 MHz，逐漸提高到200 MHz、333 MHz、466 MHz⋯⋯看起來它們可以不斷地提高CPU的速度，也就是可以不斷地提高CPU的性能。但到2004年時，由於技術限制，CPU速度的提高不能持續下去的趨勢已經很明顯了。這就需要其他技術來繼續提供更高的性能。CPU製造商的解決方案是將兩個CPU放在一個CPU內，即使這兩個CPU的工作速度都低於單個CPU。例如，與工作在300 MHz速度上的單核CPU相比，以200 MHz速度工作的兩個CPU（製造商稱它們為核心）加在一起每秒可以執行更多的計算（也就是說，直觀上看2×200 > 300）。

聽上去像夢一樣的「單CPU多核心」的故事變成了現實，這意味著程序員現在必須學習並行編程方法來利用這兩個核心。如果一個CPU可以同時執行兩個程序，那麼程序員必須編寫這兩個程序。但是，這可以轉化為兩倍的程序運行速度嗎？如果不能，那我們的2×200 > 300的想法是有問題的。如果一個核心沒有足夠的工作會怎麼樣？也就是說，只有一個核心是真正忙碌的，而另一個核心卻什麼都不做？這樣的話，還不如用一個300 MHz的單核。引入多核後，許多類似的問題就非常突出了，只有通過編程才能高效地利用這些核心。

核心越多，並行性越高
程序員不能簡單地忽略CPU製造商每年推出的更多數量的核心。2015年，英特爾在市場上推出8核台式機處理器i7-5960X[11]和10核工作站處理器，如Xeon E7-8870 [14]。很明顯，這種多核狂熱在可預見的未來會持續下去。並行編程從2000年年初的一種奇異的編程模型轉變為2015年唯一被接受的編程模型。這種現象並不局限於台式電腦。在移動處理器方面，iPhone和Android手機都有2個或4個核。預計未來幾年，移動領域的核心數量將不斷增加。

那麼，什麼是線程？要回答這個問題，讓我們來看看8核INTEL CPU i7-5960X [11]。 INTEL的文檔說這是一個8C/16T CPU。換句話說，它有8個核心，但可以執行16個線程。你也許聽到過並行編程被錯誤地稱為多核編程。正確的術語應該是多線程編程。這是因為當CPU製造商開始設計多核架構時，他們很快意識到通過共享一些核心資源（如高速緩存）來實現在一個核心中同時執行兩項任務並不困難。

類比1.1：核心與線程

圖1-1顯示了兩個兄弟Fred和Jim，他們是擁有兩台拖拉機的農民。每天，他們開車從農舍到椰子樹所在的地方，收獲椰子並把它們帶回農舍。他們用拖拉機內的錘子來收獲（處理）椰子。整個收獲過程由兩個獨立但有序的任務組成，每個任務需要30秒：任務1是從拖拉機走向椰子樹，每次帶回1顆椰子。任務2是用錘子敲碎（處理）它們，並將它們存放在拖拉機內。Fred每分鍾可以處理1顆椰子，而Jim每分鍾也可以處理1顆椰子。綜合起來，他們倆每分鍾可以處理2顆椰子。

一天，Fred的拖拉機發生了故障。他把拖拉機留在修理廠，並把椰子錘忘在了拖拉機內。回到農舍的時候已經太遲了，但他們仍然有工作要做。只使用Jim的拖拉機和裡面的1把椰子錘，他們還能每分鍾處理2顆椰子嗎？

核心與線程
讓我們來看看圖1-1中描述的類比1.1。如果收獲1顆椰子需要完成兩個連續的任務（我們將它們稱為線程）：線程1從樹上摘取1顆椰子並花費30秒將它帶回拖拉機，線程2花費30秒用拖拉機內的錘子敲碎（處理）該椰子，這樣可以在60秒內收獲1顆椰子（每分鍾1顆椰子）。如果Jim和Fred各自都有自己的拖拉機，他們可以簡單地收獲兩倍多的椰子（每分鍾2顆椰子），因為在收獲每顆椰子時，他們可以共享從拖拉機到椰子樹的道路，並且他們各自擁有自己的錘子。

在這個類比中，一台拖拉機就是一個核心，收獲一顆椰子就是針對一個數據單元的程序執行。椰子是數據單元，每個人（Jim、Fred）是一個執行線程，需要使用椰子錘。椰子錘是執行單元，就像核心中的ALU一樣。該程序由兩個互相依賴的線程組成：在線程1執行結束之前，你無法執行線程2。收獲的椰子數量意味著程序性能。性能越高，Jim和Fred銷售椰子掙的錢就越多。可以將椰子樹看作內存，你可以從中獲得一個數據單元（椰子），這樣在線程1中摘取一顆椰子的過程就類似於從內存中讀取數據單元。

並行化更多的是線程還是核心
現在，讓我們看看如果Fred的拖拉機發生故障後會發生什麼。過去他們每分鍾都能收獲兩顆椰子，但現在他們只有一台拖拉機和一把椰子錘。他們把拖拉機開到椰子樹附近，並停在那兒。他們必須依次地執行線程1（Th1）和線程2（Th2）來收獲1顆椰子。他們都離開拖拉機，並在30秒內走到椰子樹那兒，從而完成了Th1。他們帶回挑好的椰子，現在，他們必須敲碎椰子。但因為只有1把椰子錘，他們不能同時執行Th2。Fred不得不等Jim先敲碎他的椰子，並且在Jim敲碎後，他才開始敲。這需要另外的30+30秒，最終他們在90秒內收獲2顆椰子。雖然效率不如每分鍾2顆椰子，但他們的性能仍然從每分鍾1顆提升至每分鍾1.5顆椰子。

收獲一些椰子後，Jim問了自己一個問題：「為什麼我要等Fred敲碎椰子？當他敲椰子時，我可以立即走向椰子樹，並摘獲下1顆椰子，因為Th1和Th2需要的時間完全相同，我們肯定不會遇到需要等待椰子錘空閑的狀態。在Fred摘取1顆椰子回來的時候，我會敲碎我的椰子，這樣我們倆都可以是100%的忙碌。」這個天才的想法讓他們重新回到每分鍾2顆椰子的速度，甚至不需要額外的拖拉機。重要的是，Jim重新設計了程序，也就是線程執行的順序，讓所有的線程永遠都不會陷入等待核心內部共享資源（比如拖拉機內的椰子錘）的狀態。正如我們將很快看到的，核心內部的共享資源包括ALU、FPU、高速緩存等，現在，不要擔心這些。

我在這個類比中描述了兩個配置場景，一個是2個核心（2C），每個核心可以執行一個單線程（1T）；另一個是能夠執行2個線程（2T）的單個核心（1C）。在CPU領域將兩種配置稱為2C/2T與lC/2T。換句話說，有兩種方法可以讓一個程序同時執行2個線程：2C/2T（2個核心，每個核心都可以執行1個線程—就像Jim和Fred的兩台單獨的拖拉機一樣）或者lC/2T（單個核心，能夠執行2個線程—就像Jim和Fred共享的單台拖拉機一樣）。盡管從程序員的角度來看，它們都意味著具有執行2個線程的能力，但從硬體的角度來看，它們是非常不同的，這要求程序員充分意識到需要共享資源的線程的含義。否則，線程數量的性能優勢可能會消失。再次提醒一下：全能的INTEL i7-5960X [11] CPU是8C/l6T，它有8個核心，每個核心能夠執行2個線程。

圖1-2顯示了三種情況：a）是具有2個獨立核心的2C/2T情況；b）是具有糟糕編程的1C/2T情況，每分鍾只能收獲1.5顆椰子；c）是對椰子錘的需求永遠不會同時發生的順序正確版本，每分鍾可以收獲2顆椰子。

核心資源共享的影響
Jim為自己的發現感到自豪，他們的速度提高到每分鍾2顆椰子，Jim希望繼續創造一些方法來用一台拖拉機完成更多的工作。一天，他對Fred說：「我買了一把新的自動椰子錘，它在10秒內就能敲碎1顆椰子。」他們對這一發現非常滿意，立即出發並將拖拉機停在椰子樹旁。這次他們知道在開始收獲前必須先做好計劃⋯⋯

Fred問道：「如果我們的Th1需要30秒，而Th2需要10秒，並且我們唯一需要共享資源的任務是Th2（椰子錘），我們應該如何收獲椰子？」答案對他們來說很清楚：唯一重要的是線程的執行順序（即程序的設計），應確保他們永遠不會遇到兩人同時執行Th2並需要唯一的椰子錘（即共享核心資源）的情況。換句話說，它們的程序由兩個互相依賴的線程組成：Th1需要30秒，並且不需要共享（內存）資源，因為兩個人可以同時步行到椰子樹。Th2需要10秒並且不能同時執行，因為他們需要共享（核心）資源：椰子錘。由於每顆椰子需要30+10=40秒的總執行時間，他們能夠期望的最好結果是40秒收獲2顆椰子，如

圖1-2 d所示。如果每個人都按順序執行Th1和Th2，且不等待任何共享資源，則會發生這種情況。所以，他們的平均速度將是每分鍾3顆椰子（即每顆椰子平均20秒）。

內存資源共享的影響
用新的椰子錘實現了每分鍾收獲3顆椰子後，Jim和Fred第二天開始工作時看到了可怕的一幕。因為昨晚的一場大雨阻塞了半邊道路，從拖拉機到椰子樹的道路今天只能由一個人通行。所以，他們再次制訂計劃⋯⋯現在，他們有2個線程，每個線程都需要一個不能共享的資源。Th1（30秒—表示為30s）只能由一人執行，而Th2（10s）也只能由一人執行。怎麼辦？

考慮多種選擇後，他們意識到其速度的限制因素是Th1，他們能達到的最好目標是30秒收獲1顆椰子。當可以同時執行Th1（共享內存訪問）時，每個人可以順序地執行10+30s，並且兩個人都可以持續運行而無須訪問共享資源。但是現在沒有辦法對這些線程進行排序。他們能夠期望的最好結果是執行10+30s並等待20s，因為在此期間兩人都需要訪問內存。他們的速度回到平均每分鍾2顆椰子，如圖1-2 e所示。

這場大雨使他們的速度降低到每分鍾2顆椰子。Th2不再重要，因為一個人可以不慌不忙地敲椰子，而另一個人正在去摘取椰子的路上。Fred提出了這樣一個想法：他們應該從農舍再拿一把（較慢）椰子錘來幫忙。然而，這對於此時的情況絕對沒有幫助，因為收獲速度的限制因素是Th1。這種來自於某個資源的限制因素被稱為資源競爭。這個例子展示了當訪問內存是我們程序執行速度的限制因素時會發生什麼。處理數據的速度有多快（即核心運行速度）已無關緊要。我們將受到數據獲取速度的限制。即使Fred有一把可以在1秒鍾內敲碎椰子的椰子錘，但如果存在內存訪問競爭，他們仍然會被限制為每分鍾2顆椰子。在本書中，我們將區分兩種不同類型的程序：核心密集型，該類型不大依賴於內存訪問速度；存儲密集型，該類型對內存訪問速度高度敏感，正如我剛才提到的那樣。

第一個串列程序
我們已經理解了椰子世界中的並行編程，現在是時候將這些知識應用於真實計算機編程了。我會先介紹一個串列（即單線程）程序，然後將其並行化。我們的第一個串列程序imf?lip.c讀入圖1-3（左）中的小狗圖片並將其水平（中）或垂直（右）翻轉。為了簡化程序的解釋，我們將使用Bitmap（BMP）圖像格式，並將結果也輸出為BMP格式。這是一種非常容易理解的圖像格式，可以讓我們專注於程序本身。不要擔心本章中的細節，它們很快就會被解釋清楚，目前可以只關注高層的功能。

imflip.c源文件可以在Unix提示符下編譯和執行，如下所示：

gcc imflip.c -o imflip
./imflip dogL.bmp dogh.bmp V
在命令行中用「H」指定水平翻轉圖像（圖1-3中），用「V」指定垂直翻轉（圖1-3右側）。你將看到如下所示的輸出（數字可能不同，取決於你電腦的速度）：

Input BMP File name : dogL.bmp (3200×2400)
Output BMP File name : dogh.bmp (3200×2400)
Total execution time : 81.0233 ms (10.550 ns per pixel)
運行該程序的CPU速度非常快，以致我必須將原始的640×480的圖像dog.bmp擴展為3200×2400的dogL.bmp，這樣它的運行時間才能被測量出來；dogL.bmp的每個維度擴大到原來的5倍，因此比dog.bmp大25倍。統計時間時，我們必須在圖像翻轉開始和結束時記錄CPU的時鍾。

理解數據傳輸速度
從磁碟讀取圖像的過程（無論是SSD還是硬碟驅動器）應該從執行時間中扣除，這很重要。換句話說，我們從磁碟讀取圖像，並確保它位於內存中（在我們的數組中），然後只統計翻轉操作所需的時間。由於不同硬體部件的數據傳輸速度存在巨大差異，我們需要分別分析在磁碟、內存和CPU上花費的時間。

在本書將要編寫的眾多並行程序中，我們重點關注CPU執行時間和內存訪問時間，因為我們可以控制它們。磁碟訪問時間（稱為I/O時間）通常在單線程中就達到極限，因而幾乎看不到多線程編程的好處。另外，請記住，當我們開始GPU編程時，較慢的I/O速度會嚴重困擾我們，因為I/O是計算機中速度最慢的部分，並且從CPU到GPU的數據傳輸要通過I/O子系統的PCI express匯流排進行，因此我們將面臨如何將數據更快地提供給GPU的挑戰。沒有人說GPU編程很容易！為了讓你了解不同硬體部件的傳輸速度，我在下面列舉了一些：

典型的網卡（NIC）具有1 Gbps的傳輸速度（千兆比特每秒或一億比特每秒）。這些卡俗稱「千兆網卡」或「Gig網卡」。請注意，1 Gbps只是「原始數據」的數量，其中包括大量的校驗碼和其他同步信號。傳輸的實際數據量少於此數量的一半。我的目的是給讀者一個大致的概念，這個細節對我們來說並不重要。

即使連接到具有6 Gbps峰值傳輸速度的SATA3介面，典型的硬碟驅動器（HDD）也幾乎無法達到1 Gbps〜2 Gbps的傳輸速度。HDD的機械讀寫性質根本不能實現快速的數據訪問。傳輸速度甚至不是硬碟的最大問題，最大問題是定位時間。HDD的機械磁頭需要一段時間在旋轉的金屬柱面上定位需要的數據，這迫使它在磁頭到達數據所在位置前必須等待。如果數據以不規則的方式分布（即碎片式的存放），則可能需要毫秒（ms）級的時間。因此，HDD的傳輸速度可能遠遠低於它所連接的SATA3匯流排的峰值速度。

連接到USB 2.0埠的快閃記憶體磁碟的峰值傳輸速度為480 Mbps（兆比特每秒或百萬比特每秒）。但是，USB 3.0標准具有更快的5 Gbps傳輸速度。更新的USB 3.1可以達到10 Gbps左右的傳輸速率。由於快閃記憶體磁碟使用快閃記憶體構建，它不需要查找時間，只需提供地址即可直接訪問數據。

典型的固態硬碟（SSD）可以連接在SATA3介面上，達到接近4 Gbps〜5 Gbps的讀取速度。因此，實際上SSD是唯一可以達到SATA3介面峰值速度的設備，即以預期的6 Gbps峰值速率傳輸數據。

一旦數據從I/O（SDD、HDD或快閃記憶體磁碟）傳輸到CPU的內存中，傳輸速度就會大大提高。已發展到第6代的Core i7系列（i7-6xxx），更高端的Xeon CPU使用DDR2、DDR3和DDR4內存技術，內存到CPU的傳輸速度為20 GBps〜60 GBps（千兆位元組每秒）。注意這個速度是千兆位元組。一個位元組有8個比特，為與其他較慢的設備進行比較，轉換為存儲訪問速度時為160 Gbps〜480 Gbps（千兆比特每秒）。

正如我們將在第二部分及以後所看到的，GPU內部存儲器子系統的傳輸速度可以達到100 GBps〜1000 GBps。例如，新的Pascal系列GPU就具有接近後者的內部存儲傳輸速率。轉換後為8000 Gbps，比CPU內部存儲器快一個數量級，比快閃記憶體磁碟快3個數量級，比HDD快近4個數量級。

imflip.c中的main( )函數
代碼1.1中所示的程序會讀取一些命令行參數，並按照命令行參數垂直或水平地翻轉輸入圖像。命令行參數由C放入argv數組中。

clock( )函數以毫秒為單位統計時間。重復執行奇數次（例如129次）操作可以提高時間統計的准確性，操作重復次數在"#define REPS 129"行中指定。該數字可以根據你的系統更改。

ReadBMP( )函數從磁碟讀取源圖像，WriteBMP( )將處理後的（即翻轉的）圖像寫回磁碟。從磁碟讀取圖像和將圖像寫入磁碟的時間定義為I/O時間，我們從處理時間中去除它們。這就是為什麼我在實際的圖像翻轉代碼之間添加"start = clock( )"和"stop = c1ock( )"行，這些代碼對已在內存中的圖像進行翻轉操作，因此有意地排除了I/O時間。

在輸出所用時間之前，imf?lip.c程序會使用一些free( )函數釋放所有由ReadBMP( )分配的內存以避免內存泄漏。

代碼1.1：imflip.c的main( ){⋯}

imflip.c中的main( )函數讀取3個命令行參數，用以確定輸入和輸出的BMP圖像文件名以及翻轉方向（水平或垂直）。該操作會重復執行多次（REPS）以提高計時的准確性。

垂直翻轉行：FlipImageV( )
代碼1.2中的FlipImageV( )遍歷每一列，並交換該列中互為垂直鏡像的兩個像素的值。有關Bitmap（BMP）圖像的函數存放在另一個名為ImageStuff.c的文件中，ImageStuff.h是對應的頭文件，我們將在下一章詳細解釋它們。圖像的每個像素都以「struct Pixel」類型存儲，包含unsigned char類型的該像素的R、G和B顏色分量。由於unsigned char佔用1個位元組，所以每個像素需要3個位元組來存儲。

ReadBMP( )函數將圖像的寬度和高度分別放在兩個變數ip.Hpixels和ip.Vpixels中。存儲一行圖像需要的位元組數在ip.Hbytes中。FlipImageV( )函數包含兩層循環：外層循環遍歷圖像的ip.Hbytes，也就是每一列，內層循環一次交換一組對應的垂直翻轉像素。

代碼1.2：imflip.c⋯FlipImageV( ){⋯}

對圖像的行做垂直翻轉，每個像素都會被讀取並替換為鏡像行中的相應像素。

水平翻轉列：FlipImageH( )
imf?lip.c的FlipImageH( )實現圖像的水平翻轉，如代碼1.3所示。除了內層循環相反，該函數與垂直翻轉的操作完全相同。每次交換使用「struct Pixel」類型的臨時像素變數pix。

由於每行像素以3個位元組存儲，即RGB、RGB、RGB⋯⋯因此訪問連續的像素需要一次讀取3個位元組。這些細節將在下一節介紹。現在我們需要知道的是，以下幾行代碼：

只是讀取位於垂直的第row行和水平的第col列處的一個像素。像素的藍色分量在地址img[row][col]處，綠色分量在地址img[row][col+1]處，紅色分量在img[row][col+2]處。在下一章中我們將看到，指向圖像起始地址的指針img由ReadBMP( )為其分配空間，然後由main( )傳遞給FlipImageH( )函數。

代碼1.3：imflip.cFlipImageH( ){⋯}

進行水平翻轉時，每個像素都將被讀取並替換為鏡像列中相應的像素。