買專利賣專利找龍圖騰，真高效！ 查專利查商標用IPTOP,全免費！專利年費監(jiān)控用IP管家,真方便！

龍圖騰網獲悉上海科技大學申請的專利高能效FPGA實現的亂序并行最大流\最小割方法獲國家發(fā)明授權專利權，本發(fā)明授權專利權由國家知識產權局授予，授權公告號為：CN116302495B 。

龍圖騰網通過國家知識產權局官網在2025-08-22發(fā)布的發(fā)明授權授權公告中獲悉：該發(fā)明授權的專利申請?zhí)?專利號為：202310121083.9，技術領域涉及：G06F9/50；該發(fā)明授權高能效FPGA實現的亂序并行最大流\最小割方法是由閆光耀;劉心哲;哈亞軍;汪輝設計研發(fā)完成，并于2023-02-15向國家知識產權局提交的專利申請。

本高能效FPGA實現的亂序并行最大流\最小割方法在說明書摘要公布了：本發(fā)明公開了一種高能效FPGA實現的亂序并行最大流\最小割方法。本發(fā)明將一個單層大型二維格狀圖折疊成一個多層小型格狀圖。此方法有兩重好處：折疊網格架構可以儲存并處理一個尺寸遠大于處理器陣列尺寸的格狀圖；此架構還賦予二維處理器陣列垂直方向的自由度，使其可以利用垂直方向的自由度提高架構的并行潛力。通過本發(fā)明提出的折疊網格架構，使一個小尺寸的處理器陣列擁有處理一個尺寸遠大于它的格狀圖的能力。同時此折疊網格架構可以利用折疊的軸對稱性，大量減少數據在處理器陣列中的跨邊界傳輸，從而減少數據移動帶來的額外開銷。本發(fā)明還提出了一種亂序并行執(zhí)行技術，此技術可以充分挖掘折疊網格架構中的并行潛力。

本發(fā)明授權高能效FPGA實現的亂序并行最大流\最小割方法在權利要求書中公布了：1.一種高能效FPGA實現的亂序并行最大流\最小割方法，其特征在于，包括以下步驟： 步驟1、將格狀圖按照處理器陣列的大小預處理成為折疊網格數據結構，設H,W為格狀圖的尺寸，h,w為處理器陣列的尺寸，X,Y為格狀圖中節(jié)點的坐標，其中X∈[1,H]，Y∈[1,W]，則預處理過程包括以下步驟： 步驟101、將格狀圖中的節(jié)點坐標X,Y轉換至處理器陣列坐標系，轉換后的坐標為x,y，其中，x∈[1,h]，y∈[1,w]；經過坐標轉換后，將一張大型格狀圖的所有節(jié)點折疊映射至一個多層小型格狀圖中，且小型格狀圖的尺寸為處理器陣列的尺寸； 步驟102、按照轉換后的處于處理器陣列坐標系下的節(jié)點坐標，將步驟101獲得的多層小型格狀圖的數據輸入至加速器當中，對應相同坐標的格狀圖節(jié)點儲存在相同處理器當中，同時輸入h,w、與作為參數，ceila指返回大于或等于a的最小整數，其中，h,w用來初始化加速器中的輸入輸出過程中具體的時鐘延遲，與用來判斷當前處理的節(jié)點數據是否被鏡像，且坐標用于表示多層小型格狀圖的具體某一層； 步驟2、多層小型格狀圖中每個節(jié)點包含自身最多能夠容納多少流量的ef數據、指向四周節(jié)點的邊的容量edge數據、節(jié)點高度h數據以及還指向虛擬的匯的邊的容量sink，這些數據在輸入階段按照處理器陣列坐標的順序儲存在對應處理器當中，當加速器載入全部數據之后進行一次全局重標簽操作，其中，處理器單元采用基于FIFO的亂序執(zhí)行技術處理每一層小型格狀圖： 在基于FIFO的亂序執(zhí)行技術中，執(zhí)行全局重標操作時：遍歷小型格狀圖中所有節(jié)點，若小型格狀圖中節(jié)點的容量sink數據不為0，則將這些節(jié)點初始化為種子點，并將它們全部放入FIFO隊列當中，每次從FIFO隊列中取出一個節(jié)點進行計算，將當前節(jié)點的節(jié)點高度h數據更新為從FIFO隊列中讀取到的高度加1； 若當前節(jié)點指向FIFO隊列中緩存節(jié)點的邊的容量edge數據大于0，則增長此節(jié)點；當所有處理器節(jié)點中的FIFO隊列都為空時，全局重標簽操作完成，同時，在執(zhí)行過程中，若節(jié)點中ef數據大于0時，則被儲存進下一步驟Push操作的待處理FIFO當中； 步驟3、若Push操作的待處理FIFO不為空的，則執(zhí)行Push操作來完成推流操作。

如需購買、轉讓、實施、許可或投資類似專利技術，可聯系本專利的申請人或專利權人上海科技大學，其通訊地址為：201210 上海市浦東新區(qū)華夏中路393號；或者聯系龍圖騰網官方客服，聯系龍圖騰網可撥打電話0551-65771310或微信搜索“龍圖騰網”。