[發明專利]一種基于片上網絡的構造啟發式映射方法

有效

• 申請號: 202110643764.2
• 申請日: 2021-06-09
• 公開（公告）號: CN113360450B
• 公開（公告）日: 2022-09-20
• 發明（設計）人: 黃以華;張遠山;陳清坤;黃文津
• 申請（專利權）人: 中山大學
• 主分類號: G06F15/78
• 分類號: G06F15/78
• 代理公司: 廣州粵高專利商標代理有限公司 44102
• 代理人: 劉俊

1.一種基于片上網絡的構造啟發式映射方法，其特征在于，包括以下步驟：

S1：對于一個包含N個任務和M個通信需求的應用，根據M個通信需求劃分為M個兩兩任務組成的任務集群；

S2：對于劃分后的M個任務集群，首先根據兩兩任務之間的各個通信需求w_i,j的大小做一個排序，然后從高到低開始逐個遍歷這些任務集群，獲取各種任務集群映射結果，w_i,j為表示任務i與任務j之間的通信需求量值；由于一個任務不僅僅只與另一個任務存在通信需求，因此在遍歷M個任務集群的過程中，每個任務集群中的兩個任務已被映射與否存在如下狀態：1)兩個任務均未映射、2)存在一個任務已被映射、3)兩個任務已被映射但分屬于不同的任務集群、4)兩個任務已被映射且都屬于同一任務集群；

S3：對于步驟S2獲得的各種任務集群映射結果，根據熱阻模型對各個任務集群對應的處理塊做一次溫度的估計，假如某處理塊的溫度超出上限，回溯并增大該處理塊對應的任務集群中兩個任務的通信距離，以保證映射結果滿足芯片的熱可靠性，最終遍歷完M個任務集群后，選擇占用芯片面積最小且滿足溫度限制的任務集群映射結果作為最終的映射結果；

所述步驟S2中，對于狀態1)的處理方式如下：

若兩個任務均未映射，隨機挑選兩個相鄰的空閑的處理器單元作為這兩個任務的映射結果，此時這兩個處理器單元的距離為最小值1；

所述步驟S2中，對于狀態2)的處理方式如下：

若存在一個任務已被映射，那么將未被映射的任務加入到已經被分配的任務所在的集群當中，即兩個任務集群合并成一個更大的任務集群，且在原先集群的映射結果這一基礎上分配距離已映射任務所在處理器最近的且空閑的處理器單元；若存在多個等距的未接受映射任務的處理器，這可能會產生多種等效的映射結果，使得接受映射任務后的兩個處理器的通信距離相等，為了能夠快速獲得最終的映射結果，這些等效的映射結果最多僅隨機保存30種；

所述步驟S2中，對于狀態3)的處理方式如下：

若兩個任務已被映射但分屬于不同的兩個任務集群，合并這兩個任務集群，且在不改變原兩任務集群的各映射結果相對位置的這一基礎上，即在不改變已經映射的任務之間通信需求的距離這一基礎上，通過平移或者旋轉其中一個任務集群的映射結果來使得這兩個任務所在的處理器之間的通信距離最小，這種任務集群映射結果的拼接方式同樣可能導致多種等效的拼接結果，使得拼接后任務集群的各個映射結果通信功耗相等，為了加快獲得最終的映射結果，這些等效的映射結果最多僅隨機保留30種；

所述步驟S2中，對于狀態4)的處理方式如下：

若兩個任務已被映射且都屬于同一任務集群，保留所有這一集群中這兩個任務所在處理器之間距離較小的映射結果，其余的該集群的映射結果拋棄。

2.根據權利要求1所述的基于片上網絡的構造啟發式映射方法，其特征在于，所述步驟S1中，對于一個包含N個任務和M個通信需求的應用，所求解的應用映射結果即為由N個任務組成的任務集群的映射結果，將任務集群的映射結果分解為各個任務集群的映射結果；將應用根據M個通信需求劃分為M個兩兩任務組成的任務集群，在逐步的任務集群映射過程中，這些任務集群互相合并以擴展成原始的由N個任務組成的應用，同時各個任務集群的映射結果也通過拼接構成原應用的映射結果。

3.根據權利要求2所述的基于片上網絡的構造啟發式映射方法，其特征在于，所述步驟S2中，對于劃分后的M個任務集群，首先根據兩兩任務之間的各個通信需求w_i,j的大小做一個排序，優先將較大通信需求w_i,j所對應的兩個任務i,j映射到片上網絡的鄰接的兩個處理器單元中，使得兩個任務在處理器單元之間的通信距離最小，即使得片上網絡中這兩個處理器單元的曼哈頓距離dist(r_i,r_j)＝1，在這M個任務集群的遍歷結束后，M個任務集群最終將合并成一個由N個任務組成的集群，這N個任務的映射結果分別獲得并逐步拼接。