[發明專利]消息路由方案

有效

• 申請號: 200880014982.2
• 申請日: 2008-03-13
• 公開（公告）號: CN101689172A
• 公開（公告）日: 2010-03-31
• 發明（設計）人: 戴維·梅
• 申請（專利權）人: XMOS有限公司
• 主分類號: G06F15/173
• 分類號: G06F15/173;G06F15/80
• 代理公司: 北京康信知識產權代理有限責任公司
• 代理人: 余 剛;吳孟秋

技術領域

本發明涉及在處理器之間路由消息，特別涉及一種在處理器陣 列的各節點間路由消息的方案或協議。

背景技術

如圖1所示，集成電路1可被構造為處理器核(tile)2的陣 列，每個處理器核包括一個獨立的處理器4、存儲器6和通信器8。 多個處理器核2之間通過在芯片1內傳輸數據和控制消息的內部連 線10進行連接。芯片上少量的處理器核通過外部連線12與外部設 備耦合。可選地，或者另外，不同芯片上的處理器可以排列在一起 來形成一個電路。

這種體系結構的優點在于，通過在設計階段將若干較小的模塊 化處理器連接起來，廠商可以依據考慮中的應用或設備的處理與存 儲要求，甚至是它們特殊的成本、功率和區域目標(area?target)， 容易地創造一種具有特殊性能的芯片或電路。

然而，通過陣列路由消息也存在一個困難。消息可能被延遲， 可能未按最有效的路徑進行路由，或者也可能被死鎖。此外，在大 的陣列中，路由協議可能會變得復雜而難以使用。

發明內容

根據本發明的一個方面，提供了一種處理器節點陣列，每個節 點具有一個在陣列中標識自己的各自本地節點地址，每個本地節點 地址包括多個尋址重要性(addressing?significance尋址有效性) 從最高到最低順序排列的部分，并且每個節點包括：用于將本地節 點地址的每個部分映射到各個路由方向的映射裝置，以及一個用于 接收含有標識目標節點的目標節點地址的消息的切換裝置，該切換 裝置包括：用于比較本地節點地址與目標節點地址以識別最重要的 非匹配部分的裝置，以及裝置，用于在本地節點地址與目標節點地 址不匹配的情況下，沿該映射裝置映射到本地節點地址的最重要的 非匹配部分的方向將消息路由到另一個節點。優選地，但非必要地， 每個所述部分是一位。

令人驚訝地是，發明人已經發現了通過將路由方向映射到節點 地址的各個位上，就可以提供一種有效、快速、易實現的并免死鎖 的在n維處理器陣列中路由消息的協議。另一優點是，相同的簡單 方案對于具有任意數量的維度的任意尺寸的陣列都有效。

在實施例中，切換裝置可以被配置成按每次一位的方式執行所 述比較，并在遇到最重要非匹配位時中止比較。目標節點地址可以 是切換裝置所接收消息的最前面部分。目標節點地址可以被切換裝 置按從最重要位到最不重要位的順序進行接收。

這些實施例是非常有益的，因為在許多節點處，切換裝置在將 消息轉發到另外一個節點之前僅需要讀取該消息的最前面幾位。由 于地址在消息剩余部分到達前就可以起作用，本技術有助于特快的 “蟲孔路由”(wormhole?routing)。這樣切換裝置就可以迅速地以 最小延遲建立起消息的路由。

映射裝置可以包括一路由查詢表。路由查詢表可以是軟件可編 程的。映射裝置可以包括一種路由算法。

多個節點可以排列成一個至少兩維、至少三維或者至少四維的 陣列。

每個節點可以包含至少一個本地處理器，并且切換裝置可以被 配置成在本地節點地址與目標節點地址匹配的情況下，將消息路由 到本地處理器之一。切換裝置可以被配置成一旦檢測到匹配并在將 消息路由到一個處理器之前，丟棄目標節點地址。

至少一個節點可以包括多個處理器，此外消息還可以包括一個 標識節點內目標處理器的目標處理器地址，并且切換裝置可以被配 置成在目標節點地址與本地節點地址匹配的情況下，將消息路由到 目標處理器。切換裝置可以被配置成在將消息路由到目標處理器之 前，丟棄目標處理器地址。

在至少一個節點處的至少一個處理器可以包括多個I/O通道， 消息可進一步包括一個標識處理器內目標通道的目標通道地址，并 且切換裝置可以被配置成在目標節點地址與本地節點地址匹配的 情況下，將消息路由到目標通道。

切換裝置可以被配置成一旦那些位與本地節點地址相匹配，就 從目標節點地址中丟棄一位或多位。例如，節點地址中涉及一個特 定維度的部分，可以在消息位置被縮小到該維度內的具體坐標時被 丟棄。