向量機器模型

並行計算的一種理論模型，引進這種模型的主要目的是便於從理論上對各種問題並行計算的現實可能性和並行計算時所需的時間、空間等資源作定量的分析。一個向量機器由 k個向量和一個程式所組成。每個向量可以存儲一個左邊無限的 0,1序列。這個序列除了有限多位以外全都相等。也就是說，左邊是一串無限多個0或一串無限多個1，只有右邊有限多位是有變化的。有變化部分的位數稱為這一內容的長度。把這樣一個二進序列解釋為整數時，左邊無限多個0被解釋為正號,無限多個 1被解釋成負號。其餘有變化的部分按普通二進制表示理解。例如向量…1110101表示-5，…0001101表示+13。兩者的長度都是4。

向量機器模型

正文

向量機器可以採用下列各條指令來編程式：① A←ɑ,把一個常向量α送入A；②A←～B,把B向量內容取反碼（1變成0,0變成1）後送入A；③A←B∨C,B和C的相應位作邏輯加後送入A的相應位。④A←B↑C（或A←B↓C）,B的內容左移C位送入A。此處C的內容按整數意義理解。如果為負則表示右移，左移時右端補0,右移時移出的信息不再保留。A←B↓C表示右移。
除此之外，一個向量機器還可以判斷某個向量的內容是否全0，以實現條件轉移。
設W 是一個長度為 n-1的 0，1串,下面的向量機器（見圖）把形為…0001W 的字轉換成字。原始數據和答案都是放在A中。

向量機器模型

向量機器每條指令的執行，都是一種並行的計算。因此，從開始運算到停機所執行的指令總條數可算作並行時間，各向量內容長度之和在運行過程中的最大值稱為空間。串列時間的定義是執行各條指令的運算量的總和，而每條指令的運算量的定義為參加運算的向量的長度之和。
藉助於這個模型可證明下面的並行計算論題：一個問題類如果能在T(n)的一個多項式的並行時間內計算出來，若且唯若它可以在T(n)的一個多項式的空間內被串列機器計算出來。

配圖

相關連線