2011年8月26日 星期五

423 - MPI Maelstrom



BIT研究單位最近買了一台超級電腦"阿波羅",擁有32位元處理器、分散式記憶體架構、階層式訊息通道子系統。現在,Swigert請Valentine分析這台超級電腦的效能。

Valentine:由於阿波羅是一台分散式記憶體架構的電腦,所以記憶體的存取、通訊時間並不固定。共享相同記憶體的處理器間的訊息傳輸速度較快,但若非共用記憶體則速度上會慢很多。並且,阿波羅與本實驗室其他電腦的通訊時間還會更慢。

Swigert:那阿波羅的訊息傳遞介面的效率如何?

Valentine:也不夠好,從某一個處理器廣播訊號到另外n-1個處理器必須依序做n-1次傳輸,這種循序的傳遞方式正是扼殺效能的關鍵。

Swigert:那有什麼改善的方法嗎?

Valentine:有的,第一個處理器送訊號到另一個處理器後,這兩個處理器可同時送訊號到另外兩個處理器,以此類推。

Swigert:可以用二元樹廣播的方式!

Valentine:不盡然如此,因為任兩個處理器間的傳輸速率不盡相同,所以我們需要進一步研究如何最小化傳輸時間。

Input
輸入會給定 n 個處理器間的訊息傳遞時間,第一列為一個整數 n 表示處理器的數量,且 1 <= n <= 100。
之後會給定這 n 個處理器間的訊息傳遞時間,為一 n x n 矩陣A,每個矩陣元素可能為一整數表示傳遞時間,或為x字元表示無此傳遞通道,第 i 列第 j 行的元素Ai, j表示第 i 個處理器傳遞訊號到第 j 個處理器的時間。
處理器傳遞訊息給自已的時間為0,即Ai, i = 0。且訊息的傳遞是沒有方向性的,即Ai, j = Aj, i。輸入資訊會給定A的下三角矩陣。即第一列給定A2,1,第二列給定A3,1  A3,2,以此類推。

Output

你的程式必須輸出從一個處理器廣播到所有其他處理器所需的最小通訊時間。

Sample Input

5
50
30 5
100 20 50
10 x x 10

Sample Output

35


原文出處

沒有留言:

張貼留言