[go: up one dir, main page]

TW202429333A - 最佳化用於硬體裝置之演算法 - Google Patents

最佳化用於硬體裝置之演算法 Download PDF

Info

Publication number
TW202429333A
TW202429333A TW112137899A TW112137899A TW202429333A TW 202429333 A TW202429333 A TW 202429333A TW 112137899 A TW112137899 A TW 112137899A TW 112137899 A TW112137899 A TW 112137899A TW 202429333 A TW202429333 A TW 202429333A
Authority
TW
Taiwan
Prior art keywords
target
tensor
algorithm
training
state
Prior art date
Application number
TW112137899A
Other languages
English (en)
Other versions
TWI851438B (zh
Inventor
湯瑪斯 啓介 休伯特
黃士傑
亞歷山大 諾維科夫
阿爾侯賽因 法齊
帕雷德斯 貝爾納迪諾 羅梅拉
大衛 西爾弗
黛米斯 哈薩比斯
格熱戈茲 米哈爾 斯維瑞斯
朱利安 施里特維瑟
普許米特 柯立
穆罕默德達明 巴雷卡坦
馬特 巴洛格
魯伊茲 弗朗西斯科 耶穌 羅德里格斯
Original Assignee
英商淵慧科技有限公司
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 英商淵慧科技有限公司 filed Critical 英商淵慧科技有限公司
Publication of TW202429333A publication Critical patent/TW202429333A/zh
Application granted granted Critical
Publication of TWI851438B publication Critical patent/TWI851438B/zh

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/90—Details of database functions independent of the retrieved data types
    • G06F16/901—Indexing; Data structures therefor; Storage structures
    • G06F16/9027—Trees
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N3/00—Computing arrangements based on biological models
    • G06N3/02—Neural networks
    • G06N3/08—Learning methods
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N3/00—Computing arrangements based on biological models
    • G06N3/02—Neural networks
    • G06N3/06—Physical realisation, i.e. hardware implementation of neural networks, neurons or parts of neurons
    • G06N3/063—Physical realisation, i.e. hardware implementation of neural networks, neurons or parts of neurons using electronic means
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N3/00—Computing arrangements based on biological models
    • G06N3/02—Neural networks
    • G06N3/08—Learning methods
    • G06N3/092—Reinforcement learning

Landscapes

  • Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Biomedical Technology (AREA)
  • Biophysics (AREA)
  • Health & Medical Sciences (AREA)
  • Life Sciences & Earth Sciences (AREA)
  • Software Systems (AREA)
  • Data Mining & Analysis (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Artificial Intelligence (AREA)
  • Computational Linguistics (AREA)
  • Evolutionary Computation (AREA)
  • General Health & Medical Sciences (AREA)
  • Molecular Biology (AREA)
  • Computing Systems (AREA)
  • Mathematical Physics (AREA)
  • Databases & Information Systems (AREA)
  • Neurology (AREA)
  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)
  • Stored Programmes (AREA)

Abstract

本發明揭示一種由一或多個電腦執行之用於獲得一經最佳化演算法之方法，該經最佳化演算法(i)功能上等效於一目標演算法且(ii)當在一目標組的一或多個硬體裝置上執行時最佳化一或多個目標性質。該方法包含：初始化表示該目標演算法之一目標張量；使用具有複數個網路參數之一神經網路來產生該目標張量之一張量分解，該張量分解對一候選演算法進行參數化；當在該目標組的硬體裝置上執行該候選演算法時，針對該等目標性質中之每一者產生目標性質值；基於該候選演算法之該等目標性質值來判定針對該張量分解之一基準測試得分；自該張量分解及該基準測試得分產生一訓練實例；及將該訓練實例儲存在一訓練資料儲存裝置中以供用於更新該神經網路之該等網路參數。

Description

最佳化用於硬體裝置之演算法
本說明書係關於使用神經網路來最佳化用於硬體裝置之多重線性演算法。
多重線性映射(尤其係雙線性映射(例如，矩陣乘法))係由各種硬體裝置(例如，中央處理單元(CPU)、圖形處理單元(GPU)、張量處理單元(TPU)、特殊應用積體電路(ASIC)等等)執行之基本運算任務。
神經網路係採用一或多個非線性單元層來針對一所接收輸入預測一輸出之機器學習模型。某些神經網路包含除一輸出層之外的一或多個隱藏層。每一隱藏層之輸出用作對該網路中之下一層(亦即，下一隱藏層或輸出層)之輸入。該網路之每一層根據一組各別參數之當前值輸入自一所接收輸入產生一輸出。
本說明書描述一種由一或多個電腦執行之用於獲得一經最佳化演算法之方法，該經最佳化演算法(i)功能上等效於一目標演算法且(ii)當在一目標組的一或多個硬體裝置上執行時最佳化一或多個目標性質。
該方法包含：初始化表示該目標演算法之一目標張量；使用具有複數個網路參數之一神經網路來產生該目標張量之一張量分解，該張量分解對一候選演算法進行參數化，其中該神經網路經組態以接收一張量之一狀態作為輸入且根據該等網路參數處理該輸入以產生包含用於對該張量應用修改之一策略之一網路輸出，其中產生該張量分解包含：針對一步驟序列中之每一步驟：獲得該目標張量之一當前狀態；藉由自表示該當前狀態之一根節點開始執行具有表示該目標張量之狀態之若干節點之一狀態樹的一樹狀搜尋來判定針對該當前狀態之一目標網路輸出，其中該樹狀搜尋係由該神經網路根據該等網路參數引導的；使用針對該當前狀態之該目標網路輸出來向該目標張量應用一修改；及至少部分地基於在應用該修改之後該目標張量是否等於一零張量來判定是否終止該序列；以及在該步驟序列中之每一步驟處自應用於該目標張量之該等修改產生該張量分解；當在該目標組的硬體裝置上執行該候選演算法時，針對該等目標性質中之每一者產生目標性質值；基於該候選演算法之該等目標性質值來判定針對該張量分解之一基準測試得分；自該張量分解及該基準測試得分產生一訓練實例；以及將該訓練實例儲存在一訓練資料儲存裝置中以供用於更新該神經網路之該等網路參數。
該方法可包含：選擇一特定候選演算法作為該經最佳化演算法，該特定候選演算法係藉由使用基於針對該特定候選演算法之一基準測試得分之該神經網路產生的。
在某些實施方案中，該策略可定義對將自該張量減去之可能的秩一項之一機率分佈。
在某些實施方案中，該網路輸出可包含一返回輸出，該返回輸出定義由處於該狀態中之該張量產生之一經估計返回。該經估計返回可係一張量分解之一預期基準測試得分之一估計。該經估計返回可係一張量分解之一預期秩之一估計。
在某些實施方案中，執行該樹狀搜尋可包含：基於被指派給連接該狀態樹之節點之邊之動作得分而遍歷該等邊直至到達一葉節點，其中邊表示待應用於該目標張量之可能的修改；使用該神經網路根據該等網路參數來處理由該葉節點表示之該目標張量之一狀態以針對該葉節點產生一網路輸出；使用針對該葉節點之一策略在該葉節點處擴展該狀態樹；及針對該狀態樹之已被遍歷之每一邊：增量該邊之一訪問計數；及基於根據針對該葉節點之一返回輸出建構之一值來更新針對該邊之一動作得分。
在某些進一步實施方案中，執行該樹狀搜尋可包含：在一換位表中儲存在該樹狀搜尋期間遇到的一或多個節點；當遍歷邊時，判定一新遇到的節點表示與儲存在該換位表中之一先前遇到的節點相同的該目標張量之一狀態；及作為回應，將該新遇到的節點與該先前遇到的節點換位。
在某些實施方案中，判定來自該樹狀搜尋之該目標網路輸出可包含：若該根節點之所有邊之一總訪問計數大於一最大總訪問計數，則使用一自適應溫度方案來平滑化該根節點之邊之訪問計數。
在某些實施方案中，判定來自該樹狀搜尋之該目標網路輸出可包含：忽略該根節點的具有比該根節點的具有一最高訪問計數之一邊之一動作得分低的動作得分之邊。
在某些實施方案中，初始化該目標張量可包含對該目標張量執行基的一改變，且產生該張量分解可包含對該張量分解執行基的一逆向改變。
該方法可包含：產生一或多個合成張量之一組張量分解，其中一合成張量係一經隨機初始化的張量；自合成張量之該組張量分解產生一組合成訓練實例；及將該組合成訓練實例儲存在該訓練資料儲存裝置中以供用於更新該神經網路之該等網路參數。
該方法可包含：自該訓練資料儲存裝置擷取與一訓練目標相關聯的一張量之一訓練狀態；使用該神經網路根據該等網路參數處理該訓練狀態以產生一訓練網路輸出；判定一目標函數相對於該等網路參數之一梯度，該目標函數鼓勵該訓練網路輸出達到針對該訓練狀態之該訓練目標；及根據該梯度來更新該等網路參數。
在某些實施方案中，該經最佳化演算法可係在該目標組的硬體裝置上遞歸地執行。
在某些實施方案中，該目標演算法可計算一雙線性映射。該雙線性映射可係矩陣乘法。
在某些實施方案中，該等目標性質可包含以下各項中之至少一者：該經最佳化演算法之運算複雜度，該目標組的硬體裝置在執行該經最佳化演算法時之運行時間，該目標組的硬體裝置在執行該經最佳化演算法時之快取效能，該經最佳化演算法在於該目標組的硬體裝置上被執行時之參考區域性，或該目標組的硬體裝置在執行該經最佳化演算法時之功率消耗。
在某些實施方案中，該等目標性質可包含以下各項中之一或多者：該目標組的硬體裝置在執行該經最佳化演算法時之運行時間，該目標組的硬體裝置在執行該經最佳化演算法時之快取效能，該經最佳化演算法在於該目標組的硬體裝置上被執行時之參考區域性，或(在不包含該經最佳化演算法之運算複雜度之情況下)該目標組的硬體裝置在執行該經最佳化演算法時之功率消耗。
在某些實施方案中，該目標組的硬體裝置可係一組硬體裝置之一模擬。
在某些實施方案中，該目標組的硬體裝置可包含以下各項中之至少一者：一中央處理單元(CPU)、一圖形處理單元(GPU)、一張量處理單元(TPU)或一特殊應用積體電路(ASIC)。
該方法可包含：接收一新輸入；及藉由在該目標組的硬體裝置上執行該經最佳化演算法而對該新輸入執行該目標演算法。
本說明書中所描述之標的物之特定實施例可經實施以便實現以下優點中之一或多者。
本說明書中所揭露之系統及方法可使用一神經網路自動地獲得經最佳化多重線性演算法，例如針對一組特定硬體裝置最佳化之演算法。結果係：硬體裝置比現有演算法具有優越的效能，如藉由效能度量(例如，經降低運算複雜度、經減少運行時間、經減少功率消耗、經改良快取度量、經增加參考區域性等等)之任一組合所量測。使用本文中所揭露之機器學習技術自動產生高效演算法可超越人類直覺之領域且勝過人類設計的演算法。
附圖及下文的說明中陳述本說明書之標的物之一或多個實施例之細節。根據說明、圖式及申請專利範圍將明瞭標的物之其他特徵、態樣及優點。
圖1展示可自動地產生用於一組硬體裝置之經最佳化演算法之一實例最佳化系統100。最佳化系統100係在一或多個位置中之其中實施下文所描述之系統、組件及技術之一或多個電腦上作為電腦程式實施之一系統之一實例。
系統100接收一目標演算法來針對一目標組的一或多個硬體裝置進行最佳化，該目標組例如以下各項中之一或多者：一中央處理單元(CPU)、一圖形處理單元(GPU)、一張量處理單元(TPU)、一特殊應用積體電路(ASIC)等等。該目標演算法可描述待由硬體裝置執行之任何一組操作，唯一規定係該目標演算法可表示為一張量。亦即，該目標演算法可計算任一多重線性映射 ，其中 及 Y係有限維向量空間且 f係實施該目標演算法之一函數。
多重線性映射(尤其係雙線性映射)係可操控大量資料之基本運算任務。最佳化此等遍存任務允許硬體裝置充分利用其運算資源。舉例而言，GPU及TPU可由於其經平行化處理架構(例如，經結構化矩陣乘法、多項式乘法、迴旋、定製機器學習操作等等)而高效地執行雙線性映射。然而，針對其特定架構判定適當演算法通常依靠人類直覺，且因此係次最佳的。相比而言，系統100可自動地使用經由相對於硬體裝置之一或多個效能目標(例如，作為一加權和)之強化學習而訓練之一神經網路來產生最佳演算法(亦即，針對一特定硬體架構最佳化之一演算法)。
效能目標可由在硬體裝置上執行經最佳化演算法時之任何數量的目標性質來表徵。該等目標性質可包含對經最佳化演算法之運算複雜度之一固有量測。另一選擇係或另外，該等目標性質可包含特定於該組硬體裝置之一或多個參數(例如，取決於硬體裝置架構之參數)，以及當在硬體裝置上實施時指示經最佳化演算法之效能(諸如，運行時間、快取命中度量、參考區域性、功率消耗等等)之一或多個參數。如將更詳細地描述，系統100可即時地對此等性質進行基準測試以訓練神經網路產生以特定於該組硬體裝置之一方式最佳化任一組合的目標性質之一演算法。
此外，系統100可產生功能上等效於目標演算法之經最佳化演算法。在此情形下，「功能上等效」暗示對於每一及每個可能的輸入，經最佳化演算法計算出與目標演算法完全相同的對應輸出。換言之，經最佳化演算法係可證明正確的且不近似目標演算法。在考慮基本運算任務時，此可係一尤其有利的品質，此乃因當在硬體裝置上執行時，經最佳化演算法將不會累積錯誤。注意，術語「完全相同」用於意指對於特定數量的有效數字(例如，有效數字之數量係相乘值中之位數)係完全相同的，此乃因在乘法操作之硬體實施方案中，當兩個浮點值相乘時可出現舍入誤差。若目標演算法包含一截斷步驟，以便產生將函數 f編碼為特定數量的有效數字之一輸出，則經最佳化演算法亦可如此。
為了清晰起見，下文概述了多重線性映射之一簡要回顧，來示範一目標張量 可表示目標演算法之方式。多重線性函數 將向量空間 中之變數映射至向量空間 。另外，函數 f在每一變數 中具有線性性質，使得，
在此處， a及 b係純量。單一變數之一多重線性映射係一線性映射。兩個變數之一多重線性映射係一雙線性映射(例如，矩陣乘法)等等。
為了實施目標演算法，硬體裝置相對於某個向量基執行函數 f。該基規定在執行 f時該等硬體裝置索引變數 x α 之元素之方式。儘管可實施任一向量基，但在大多數情形下，向量空間係由線性陣列表示，此乃因此係正常情況下計算裝置索引資料結構之方式。特定而言，每一向量空間 X α 之變數可表示為行向量 ，其中 係變數之純量元素。然而，元素 本身可大體上與矩陣或張量相關聯。舉例而言， x α 可含有處於列優先階佈局或行優先階佈局中之一矩陣之若干個元素。此基提供一非常方便及強有力的框架來實施任意多重線性演算法，且因此採用在本文中之演算法之說明中。
相應地，可針對每一向量空間 選擇單范正交單位向量 之一「正準」基，以及針對 Y選擇基 。單位向量可表達為行向量，其中單一項目係1且其餘係0，
因此，每一向量空間之變數可相對於單位向量擴展為 及 。注意，每一基中之單位向量之數量取決於其各別向量空間之維度。每一向量空間可具有任意的維度。使用前述線性性質，函數 f可在此基上被參數化為，
在此情形下，參數化意指相對於索引 及 k執行函數 f。張量分量 之集合定義目標張量 。目標張量 完整地指定經選擇基中之多重線性函數 f。特定而言，分量 獨立於 且透過參數化與 f相關
在此處， 表示點積。目標張量 大體上係 階，對應於 D個不同的索引，其中 n係進入多重線性映射之變數數量。目標張量 之大小 取決於每一向量空間 X α 之維度 N α ，以及 Y之維度 N。
輸出向量 y之元素 y k 簡潔地表達為
每一 y k 計算為對元素 之積之一求和，由張量分量 擴縮。硬體裝置可藉由遍及 執行巢套迴圈來計算每一積且然後針對每一 y k 計算積之對應求和而實施目標演算法。所有此等運算皆在目標張量 中緊湊地表示。因此，目標張量 係目標演算法之一張量表示。
作為一雙線性映射之一具體的實例，考慮具有大小 N×N之矩陣 A與 B之矩陣乘法以產生相同大小的一矩陣 C=AB。為了實施針對矩陣乘法之一演算法，每一矩陣之元素可例如以列優先階或行優先階儲存在線性陣列， 、 及 中。在此情形下， 係針對維度 N 2 之向量空間形成一單範正交基之單位向量之一 N 2 集。由此，元素 、 及 在其各別矩陣 A、 B及 C中對應於每一元素。一雙線性函數 m藉由採取 a及 b作為輸入並計算 中之對應結果來實施方形矩陣乘法之一演算法。利用上文所描述之處方，每一 可表達為 與 之間乘法之一線性組合
張量分量 之集合具有 中之值且將 階之一「矩陣乘法張量」 定義為大小 。 之分量獨立於 且透過參數化與雙線性函數 m相關
因此，矩陣乘法張量 係一矩陣乘法演算法之一張量表示。一類似的處理程序大體上適用於任一雙線性映射或多重線性映射。
儘管如此，由一特定張量表示之一特定演算法可係次最佳的。例如，矩陣乘法張量 具有立方運算複雜度 ，此乃因其涉及 A之元素與 B之元素之間的 N 3 乘法，但此乘法量係非必需的。採取 N=2作為一實例，系統100可建構僅涉及7次乘法(而不是8次)之經最佳化演算法(例如，斯特拉森(Strassen)演算法)。在一演算法中減少乘法次數可係用於改良一組硬體裝置之效能之一有效的手段，此乃因乘法通常比加法運算成本更高。
系統100藉由重新參數化目標張量 產生一經最佳化演算法，且因此藉由一張量分解之方式產生目標演算法。系統100藉由將目標張量 因式分解為 R秩一項(rank-one term) 之一線性組合來獲得張量分解，
如其名稱暗示，每一秩一項之秩係秩 ，此對其可允許的形式加以限制。具有 秩一項之一張量分解被稱為一秩- 分解。相應地，目標張量 之秩據稱最多 R，或秩 。注意，一張量之秩不應與其階 D混淆，此乃因此兩者係兩個不同但有關的量。一張量之秩取決於其大小且標示其可在一張量積空間中表示之線性獨立方向之數量。換言之，秩係一張量「非簡併性」之一量測。舉例而言，具有大小 N × M之一階 D=2張量(亦即，一矩陣)具有由 約束之一最大秩。具有大小 N × M × P之一階 D=3張量具有由 約束之一最大秩等等。
一秩一項 在張量積空間中表示單一線性獨立方向且因此可總是表達為 D=n+1向量因子之一外(張量)積 ，
每一因子 及 在 及 Y之向量空間中表示單一方向。其組合係在張量積空間 中之單一線性獨立方向。
系統100相對於張量分解中之設定因子 對經最佳化演算法進行參數化。亦即，輸出向量 y之每一元素 y k 可計算為
其中，
硬體裝置可藉由遍及索引 進行迴圈來計算每一積 m r 且然後針對每一 y k 計算積之對應求和而實施一經最佳化演算法。在此情形下，遍及 r之迴圈代替遍及 之巢套迴圈，從而實現一更具運算效率的演算法。如上述方程式中所見，分解 R之秩決定運算複雜度 ，亦即，積 m r 之數量，此意味著低秩分解大體上係合意的。該等因子 之特定形式控制分解之密度，亦即，加法之次數。具有低秩分解之一目標張量 暗示目標演算法具有諸多冗餘操作(該目標演算法係高度簡併的)。系統100旨在消除此等冗餘。
圖6展示可由最佳化系統100獲得之一經最佳化矩陣乘法演算法之一實例。在此處，矩陣乘法張量 藉由因子 、 及 而重新參數化。如圖6中所見，輸入矩陣 A之元素與 B之元素之間的乘法次數受 R控制。因此，具有 之分解對應於具有經降低運算複雜度之方形矩陣乘法演算法。圖6中所展示之形式之演算法可用於使分塊矩陣相乘，例如，可利用4×4演算法使8192×8192矩陣之2048×2048大小的子矩陣相乘。此外，可在一組硬體裝置上遞歸地執行圖6之演算法以使任意大小之矩陣相乘，亦即，可以運算複雜度 使 M × M大小的矩陣相乘。因此，可利用更小大小的矩陣乘法張量之低秩分解來高效地使更大矩陣相乘。
圖1圖解說明系統100使用一分解引擎100A自神經網路產生 之張量分解同時使用一訓練引擎100B在該等分解上訓練神經網路之方式。此等程序可順序地或並行地執行以自動地收斂至低秩張量分解。注意，找到張量之低秩分解係NP困難的且在實踐中係一困難的運算任務(經常依靠於人類設計的啟發式方法之一任務)。系統100提供克服張量分解問題之一自主手段，以及針對任一組硬體裝置最佳化泛用多重線性演算法。
在找到用於一目標組硬體裝置之一經最佳化演算法之後，系統100可利用經最佳化演算法來替代目標演算法。亦即，可替代地由經最佳化演算法執行由該組硬體裝置所接收的涉及由目標演算法執行之操作之所有新輸入。結果係裝置具有優越的效能，如藉由一或多個目標性質之任一組合(亦即，由一加權和之權重定義之一組合)而量測的，例如經降低複雜度、經減少運行時間、經減少功率消耗、經改良快取度量等等。由於多重線性映射(例如，愛因斯坦求和( einsum)操作)成為諸多系統(例如，訓練大型語言模型)之瓶頸，因此對現有演算法之此等改良可產生顯著影響。隨著專門硬體裝置數量激增(預期在可預見的未來會如此)，此等定製演算法將變得愈來愈普及。若演算法及硬體設計兩者共同被最佳化，則系統100可提供甚至更高的增益。
沿著類似的路線，系統100亦可將指定經最佳化演算法之資料(例如，該組參數化因子 )發送至一不同組的硬體裝置以替代目標演算法來實施經最佳化演算法。舉例而言，若系統100獲得用於一GPU叢集中之一GPU之一經最佳化矩陣乘法演算法，則系統100可將指定經最佳化演算法之資料發送至該叢集中之所有GPU。在一個裝置上所達成的效能增強係可擴縮的，此乃因經最佳化演算法可利用相同(或類似)處理架構在任一其他裝置上實施。
現在參考由系統100所採用的神經網路。由一組網路參數 θ120參數化之神經網路經組態以接收一張量之一狀態 作為輸入並處理該狀態以產生一網路輸出 。該網路輸出包含用於對 應用修改(亦即，動作)以產生一經修改張量 之一策略 。該策略定義來自一組動作的可被應用為對 之修改以便產生 之動作 a。大體而言，策略 提供對 D=n+1個可能的因子 之一分佈，該等可能的因子可組合成可能的秩一項 。因此，一動作 對應於 D=n+1個因子之一選擇並自 減去所得秩一項，使得 。
該網路輸出亦可包含一返回輸出 。大體而言，返回輸出 針對張量處於狀態 中而提供對一預期基準測試得分之一分佈。然而，該返回輸出可替代地係一回歸值，例如對應於分佈之平均值之一預期基準測試得分。儘管如此，由於可捕獲基準測試得分之高可變性，因此模型化一分佈大體上為系統100提供經改良效能及靈活性。
一基準測試得分110表徵當在一目標組的硬體裝置上執行由一張量分解106參數化之一候選演算法108時之效能目標。如下文將更詳細地討論，基準測試得分110係向張量分解106指派一相對得分之一數字值。
在某些實施方案中，返回輸出 提供對一張量分解106之一預期秩之一分佈。在此情形下，該預期秩充當基準測試得分110之一代理量測，而不在硬體裝置上實際執行候選演算法108。此係由於張量分解106之秩 R係候選演算法108之運算複雜度 之一直接量測。由此，當單獨地最佳化複雜度時，系統100不需要參考任一特定組的硬體裝置且將傾向於收斂至低秩張量分解。
大體而言，最佳化系統100中所包含的神經網路可具有用以達成其所要功能之任一適合的架構。特定而言，神經網路可包含以任何適當的數量(例如，5、10或100層)及以任一適當的組態(例如，作為層之一線性序列)配置之任一適當的神經網路層(例如，全連接層、迴旋層、注意力層等等)。
下文概述最佳化系統100之一高階綜述。所涉及之每一程序之細節將關於圖2至圖5詳盡描述。
分解引擎(DE) 100A將一張量之一初始狀態 設定為目標張量 ，然後執行一步驟序列以產生一張量分解106。每一步驟 後之張量由一狀態 102a至102n描述。在該序列之每一步驟處，DE 100A選擇一動作 a t 並根據 a t 更新當前狀態 。動作 a t 對應於因子 之一選擇，且當前狀態藉由減去所得秩一項 來修改 。為了判定適當的動作 a t ，DE 100A在每一步驟處執行一狀態樹之一樹狀搜尋104a-n，例如一蒙地卡羅(Monte-Carlo)樹狀搜尋(MCTS)。樹狀搜尋由神經網路根據網路參數 θ120來引導，以判定針對步驟之一適合的動作 a t 。
DE 100A在每一步驟 處應用一動作 a t 直至張量在一最終步驟 處達到一零張量 。在此之後，由DE 100A所選擇的所有因子 合併成一張量分解106，該張量分解對一候選演算法108進行參數化。序列 T=R中之步驟總數等於分解106之秩，以及候選演算法108之運算複雜度 。此外，由此推論出經選擇因子之序列滿足 ，其保證候選演算法108之正確性。為了避免可能無限的序列，系統100可將步驟數限制至一最大值，在此之後終止序列。舉例而言，最大值可係目標張量 之最大秩之一上界。在某些情形下，系統100向不完全分解指派一償罰得分，以便訓練神經網路遠離此等動作序列。
系統100藉由在該組硬體裝置上可能多次地執行候選演算法108而即時地對候選演算法108進行基準測試。舉例而言，系統100可利用隨機初始化的輸入多次地執行候選演算法108且然後對效能度量求平均。另一選擇係或另外，系統100可在可並行地執行多個執行之硬體裝置之一模擬上執行候選演算法108。
系統100然後獲得一基準測試得分110，該基準測試得分表徵針對執行候選演算法108之硬體裝置之目標性質(例如，運算複雜度、參考區域性、運行時間、快取命中度量、功率消耗等等)。基準測試得分110係適當地加權正在最佳化的目標性質之目標性質值之組合(亦即，根據一加權和之權重)之一數字值。舉例而言，目標性質值可包含秩 R=T、引用的區域記憶體數量、平均運行時間、平均快取命中率、平均所消耗的能量等等中之任一者。系統100係靈活的，此乃因其支援複雜隨機且不可微分的基準測試得分110。在某些實施方案中，基準測試得分110嚴格地包含張量分解106之秩 R=T，在此情形下候選演算法108不需要在任一特定組的硬體裝置上執行。系統100然後嚴格地最佳化低秩分解，亦即，最小化運算複雜度。更佳地(另外或替代地)，基準測試得分係基於特定於該組硬體裝置且指示由該組硬體裝置對候選演算法108之對應執行之目標性質中之一或多者。
系統100自儲存在一訓練資料儲存裝置114中之張量分解106及基準測試得分110產生一訓練實例112a。基準測試得分110可加強已達成相對良好得分(例如，低秩及/或低運行時間)之張量分解106。另一選擇係或另外，系統100可產生合成訓練實例112b並將該等合成訓練實例添加至資料儲存裝置114。合成訓練實例112b對應於隨機初始化的合成張量 之張量分解。監督式學習可訓練網路來模仿合成資料集之分解。
與DE 100A順序地或並行地，訓練引擎(TE) 100B自訓練資料儲存裝置114隨機取樣一訓練張量狀態 118。TE 100B使用訓練狀態 118來更新神經網路之網路參數 θ120。訓練狀態 118可源自一訓練實例112a或一合成訓練實例112b。在前一種情形下，神經網路經由強化學習訓練。在後一種情形下，神經網路經由監督式學習訓練。一混合的訓練對策(其中神經網路在目標張量 以及合成張量 之張量分解上進行訓練)可明顯勝過單獨的每一訓練對策。儘管 與 具有非常不同的性質。TE 100B可對訓練狀態 118持續地進行取樣以持續地更新網路參數 θ120。
可藉由DE 100A利用經更新神經網路來獲得經改良張量分解106，隨後該等經改良張量分解被進行基準測試且用作TE 100B之訓練實例112a。此程序可重複，直至系統100在一最佳化器上利用(相對於目標演算法之一基線基準測試得分之)最佳可達基準測試得分110收斂一候選演算法108，在此情形下候選演算法108被最佳化。
換言之，該系統可持續更新神經網路同時產生候選演算法直至滿足一終止準則。一旦滿足該終止準則，則該系統可選擇最近產生的候選者或具有最佳基準測試得分之候選者作為經最佳化演算法。舉例而言，該準則可在基準測試得分110達到某一臨限值(基準測試得分110相對於儲存在資料儲存裝置114中之先前得分之改變可忽略不計、已經產生臨限數量的候選者、臨限量的經過時間已過去等等)時滿足。注意，系統100可獲取多個經最佳化演算法，該多個經最佳化演算法在該組硬體裝置上同樣良好地執行，亦即，其具有等效的基準測試得分。系統100或一使用者可選擇用以實施目標演算法之此等經最佳化演算法中之任一者。
圖2係用於產生目標張量 之一張量分解106之一實例程序200之一流程圖。為方便起見，程序200將描述為由位於一或多個位置中之一或多個電腦之一系統執行。舉例而言，根據本說明書適當地程式化之一分解引擎(例如，圖1之分解引擎100A)可執行程序200。
分解引擎(DE)將一張量 初始化為目標張量(202)。在某些實施方案中，在初始化 之前，DE執行基的一改變 。此可係利用張量分量上之以下變換來實現
其中 及 B係定義新基之 D= n+1可逆矩陣。可藉由對恢復的因子集執行基的一逆向改變而將所得分解轉換回至原始(正準)基。此處理程序將分集注入至系統100中，此可有助於神經網路分解張量及自張量分解學習兩者。DE可對基隨機地取樣且在此等基中並行地執行分解。為了數值穩定性，所有基矩陣可係麼模的，具有±1之行列式。
一整數索引 被設定為 之一初始值。
DE獲得張量之一當前狀態 (204)。在 之情形下，此相當於獲得在步驟202中所產生的 。
DE執行一狀態樹之一樹狀搜尋以判定針對當前狀態 之一目標網路輸出(206)。樹狀搜尋之詳情在下文中關於圖3進行描述。由神經網路引導之樹狀搜尋返回包含對動作 之一經改良策略之目標網路輸出。經改良策略提供對可能的因子 之一經改良分佈，該等可能的因子可組合成可能的秩一項 。
DE使用針對當前狀態之目標網路輸出來向當前張量狀態 應用一修改(208)。DE藉由自經改良策略 進行取樣而判定一適當的動作 a t 。動作 a t 對應於因子 之一選擇，該等因子藉由減去所得秩一項 而自張量之當前狀態修改該張量 。
DE判定經修改張量是否等於一零張量 (210)。若張量不等於零張量 ，則程序200自步驟204重複。若張量等於零張量 ，則程序200進行至步驟212。
在判定張量等於一最終反覆 之零張量 之後，DE自應用於張量之所有修改產生張量分解106 (212)。亦即，DE合併由動作 選擇的所有因子 以獲得張量分解 。
圖3係用於執行狀態樹之一樹狀搜尋(例如，一蒙地卡羅樹狀搜尋(MCTS))以判定一目標網路輸出之一實例程序300之一流程圖。為方便起見，程序300將描述為由位於一或多個位置中之一或多個電腦之一系統執行。舉例而言，根據本說明書適當地程式化之一分解引擎(例如，圖1之分解引擎100A)可執行程序300，例如作為執行方法200之步驟206之一部分。
狀態樹包含若干節點，該等節點表示一張量之狀態 ，由表示動作 a之有向邊連接。每一狀態-動作對 儲存一組邊統計資料 、 及 ，其分別對應於一訪問計數、動作值及先驗機率。
用於執行樹狀搜尋之詳細步驟由T.Hubert、J.Schrittwieser、I.Antonoglou、M.Barekatain、S.Schmitt及D.Silver之「Learning and planning in complex action spaces」提供，參見2021年之 International Conference on Machine Learning (ICML)，其中概述了 Sampled AlphaZero之一類似基於取樣的MCTS。
DE識別表示一張量之一當前狀態 之一根節點(302)。
自根節點開始，DE遍歷狀態樹直至到達表示一葉狀態 之一葉節點(304)。DE可例如藉由最大化機率性上限置信樹(PUCT)界限而基於被指派給該等邊之動作得分遍歷狀態樹。
DE評估表示葉狀態 之葉節點(306)。葉狀態 由神經網路根據網路參數 θ處理 ，以產生針對葉節點之一網路輸出。該網路輸出包含針對葉節點之一策略 且亦可包含針對葉節點之一返回輸出 。
DE擴展表示葉狀態 之葉節點(308)。該網路輸出可用以利用經連接至葉節點之新(子)節點來擴展狀態樹。新節點表示張量狀態 。具體而言，一組動作 可自針對葉節點之策略 來判定。每一動作 與因子 之一選擇及一所得秩一項 相關聯。自葉狀態 減去秩一項以產生新節點 。注意，由於巨大的動作空間(例如，在大多數所關注的情形下大於10 12)，因此該組動作 大體上自該策略取樣且不完全地枚舉。由此，系統100根據針對葉節點之策略利用 對固定數量的動作 進行取樣。
在某些實施方案中，使用返回輸出 來建構針對葉節點之一值 。該值可係返回輸出之平均值，亦即，預期基準測試得分，但更大體而言，該值可經建構以鼓勵樹狀搜尋之特定行為。舉例而言，值 可係一風險尋求值，鼓勵探索，以便找到狀態樹之最佳軌跡。為實現此目的，神經網路可產生由對應於分位數 之 輸出組成的一返回輸出。以此方式，返回輸出以針對前述分位數所預測之值之形式預測一狀態之返回分佈。為建構一風險尋求值 ，DE可使用超過75%之分位數之經預測值之平均值。分位數回歸學習之一回顧由W.Dabney、M.Rowland、M.Bellemare及R.Munos之「Distributional reinforcement learning with quantile regression」提供，參見2018年第32卷之 Proceedings of the AAAI Conference on Artificial Intelligence。
DE針對所有遍歷的邊更新邊統計資料(310)。在沿狀態樹向後傳遞之後，DE旋即對在沿該樹向下之軌跡期間遍歷之所有邊之訪問計數及動作值(例如，使用值 )進行增量。
DE自根節點執行連續軌跡直至滿足一或多個準則，例如，已過去最大時間、已評估最大數量的葉節點等等。另外，若不同的軌跡到達表示一張量之完全相同的狀態之節點，則DE可使用一換位表來重新組合該等不同的軌跡。此可頻繁地發生，此乃因動作大體上係可交換的，亦即，改變動作次序不會改變所得狀態。在此情形下，一換位表係頻繁遇到的節點之一快取。若表示一特定狀態之一節點經由一不同序列的動作複現，則DE可將該節點與來自換位表之(表示相同狀態之)一先前遇到的節點換位，從而避免重新評估彼節點下方的子樹。此大體上增加自狀態樹所收集之資訊之品質。
在來自根節點之 軌跡之後，DE判定針對當前狀態 之一目標網路輸出(312)。該目標網路輸出包含對動作之一基於取樣的經改良策略 。該經改良策略可根據根節點之邊之經正規化訪問計數來判定 ，其中 係根節點之邊之訪問計數。DE可然後使用經改良策略 來選擇一動作 a t 。
在某些實施方案中，經選擇動作 a t 下面的子樹(亦即，根節點處之經選擇邊)在下述反覆中重新用於針對 之樹狀搜尋中。
在進一步的實施方案中，樹狀搜尋使用一自適應溫度方案來平滑化經正規化訪問計數(亦即，來抑制 之相對大的值)，此乃因由於換位表及子樹複現，某些狀態可比其他狀態累積更多數量級的訪問。舉例而言，可使用一函數 來平滑化經正規化計數，其中若 ，則該函數係 且否則為1。在此處， 係表示根節點之所有邊之一最大總訪問計數之一超參數。
在更進一步的實施方案中，當返回經改良策略以用於DE之動作選擇時，樹狀搜尋忽略根節點的具有比最常被訪問邊之動作得分低之動作得分之邊。
圖4係用於自張量分解產生訓練實例之一實例程序400之一流程圖。為方便起見，程序400將描述為由位於一或多個位置中之一或多個電腦之一系統執行。舉例而言，根據本說明書適當地程式化之一最佳化系統(例如，圖1之最佳化系統100)可執行程序400。
該系統獲得由一張量分解參數化之一候選演算法(402)。
該系統在一目標組的硬體裝置上可能多次地執行該候選演算法(404)。在某些實施方案中，該候選演算法係在該組硬體裝置之一模擬上執行，在此情形下諸多模擬可並行地運行。
該系統針對硬體裝置之目標性質產生目標性質值(406)。該等目標性質表徵硬體裝置之任何數量的效能目標，例如複雜度、運行時間等等。該等目標性質值將數值指派給此等性質。舉例而言，目標性質值可包含張量分解之秩 R及在硬體裝置上執行之候選演算法之平均運行時間 B。
該系統基於目標性質值來判定針對張量分解之一基準測試得分(408)。基準測試得分可在一線性組合或非線性組合中加權目標性質值以強調特定目標性質。舉例而言，基準測試得分 G可包含秩 R及候選演算法之平均運行時間 B，即 ，其中 係控制運算複雜度與運算速度之相對重點之一使用者指定的係數。在此情形下，一高基準測試得分對應於低複雜度與快速運行時間之一組合。
該系統自張量分解及基準測試得分產生一訓練實例(410)。該訓練實例大體上包含由分解引擎(DE) 100A執行之序列 中之每一步驟處之張量之狀態 。該訓練實例亦包含自每一步驟 處之樹狀搜尋判定之目標網路輸出(亦即，經改良策略 )。
該系統將訓練實例儲存在一訓練資料儲存裝置中以供用於經由強化學習訓練神經網路(412)。訓練實例可在資料儲存裝置中相對於其基準測試得分進行分類以利用最佳相對得分來加強張量分解。在某些情形下，此意味著廢除具有低分數之訓練實例並保留具有可接受分數之訓練實例。該系統可藉由重新排序秩一項(由於求和係可交換的)而自相同的張量分解中提取額外訓練實例。特定而言，該系統可隨機地交換兩個動作以產生一額外訓練實例。此幫助系統探索先前僅在分解序列中稍後發現之動作。
另一選擇係或另外，該系統可將合成訓練實例合併至資料儲存裝置中以供用於經由監督式學習訓練神經網路。該等合成訓練實例包含隨機張量 之張量分解。該系統可隨機地取樣因子 以自對應秩一項 建構 。由此，根據定義，該等因子構成 之一張量分解。由於自秩一項 獲得隨機張量 之前述程序係基本的，因此該系統可產生一任意大的合成訓練實例集。
藉由在自訓練資料儲存裝置取樣之訓練實例上訓練神經網路的同時重複地執行程序400，神經網路將產生具有增加的基準測試得分之候選演算法。一旦滿足了用於終止訓練之一終止準則，則系統可(例如，藉由選擇最近產生的候選者或者藉由識別已經產生的該等候選者當中具有最佳基準測試得分之候選演算法)選擇使用程序400已經產生的候選演算法中之一者作為經最佳化演算法。
圖5係用於更新一神經網路之網路參數值 θ之一實例程序500之一流程圖。為方便起見，程序500將描述為由位於一或多個位置中之一或多個電腦之一系統執行。舉例而言，根據本說明書適當地程式化之一訓練引擎(例如，圖1之訓練引擎100B)可執行程序500。
訓練引擎(TE)自一訓練資料儲存裝置隨機地取樣一訓練狀態 (502)。
TE使用神經網路根據網路參數 θ處理訓練狀態 ，以產生一訓練網路輸出 (504)。
每一訓練狀態 與一訓練目標相關聯。若訓練狀態 源自一訓練實例，則訓練目標係最大化訓練策略 與針對狀態之經改良策略 之間的相似性。為實現此目的，一目標函數可包含量測 p與 之間的一發散損耗(例如，一庫爾巴克-萊布勒(Kullback–Leibler)發散損耗)之項。在某些實施方案中，訓練目標亦旨在最大化由訓練返回輸出 定義之一經估計基準測試得分與針對狀態 之一實際基準測試得分之間的相似性。舉例而言，目標函數可包含量測一分位數回歸分佈損耗之項。
另一方面，若訓練狀態 源自一合成訓練實例，則訓練目標係最大化訓練策略 與下一動作 a(亦即，下一秩一項 )之間的相似性。亦即，自訓練狀態 開始，下一動作 a係自狀態 中減去之下一秩一項 之因子 之一特定選擇。此對應於合成張量之分解中之一特定步驟。由於合成張量 係由已知的因子及秩一項建構，因此下一(最佳)動作係先驗已知的。在此情形下，目標函數可包含量測給定狀態 的動作之可能性之項，該狀態訓練神經網路以模仿合成訓練資料中之分解。
TE判定目標函數相對於網路參數 θ之一梯度(506)。
TE根據目標函數之梯度更新網路參數值 θ(508)。舉例而言，TE可使用一隨機梯度下降方法(例如，RMSprop、具有解耦權重衰減之Adam等等)以更新網路參數值。
圖7A及圖7B展示分別針對一NVidia V100 GPU與一TPU v2之運行時間最佳化之8192×8192大小的矩陣乘法演算法。亦即，系統100獲取用於使4×4矩陣相乘之候選演算法，且針對用於計算8192×8192分塊矩陣之運行時間(及複雜度)對候選演算法進行基準測試，其中每一分塊(子矩陣)對應於2048×2048矩陣。經最佳化矩陣乘法演算法根據圖6被參數化且與斯特拉森演算法進行比較。在同一硬體上相對於標準(例如，針對GPU之cuBLAS)矩陣乘法量測加速。藉由遞歸地執行經最佳化演算法，報告針對各種矩陣大小之加速(儘管僅在一個矩陣大小上最佳化演算法)。在超過200次運行中報告了中值加速，在運行中具有＜0.4%之一標準偏差。
如圖7A及圖7B中所見，系統100可定製用於特定硬體裝置(諸如GPU及TPU)之演算法。然而，如先前所提及，用於一特定硬體裝置之一經最佳化演算法在一不同的硬線裝置上由於其不同的處理架構而可能無法最佳地執行。圖7C展示在一8192×8192矩陣大小之兩種裝置上進行基準測試之兩種演算法(針對GPU及TPU定製)之加速差異。舉例而言，當針對TPU最佳化之演算法在一GPU上運行時，相對於標準矩陣乘法之加速僅係4.4%。
目標演算法可被選擇為一多重線性映射，該多重線性映射係一資料處理任務(諸如任一已知的資料處理任務)之一分量，該資料處理任務對自真實世界獲得之輸入資料(例如，感測器資料，諸如自一靜物攝影機、一視訊攝影機、一LIDAR感測器或一麥克風導出之資料)執行，及/或經執行以產生用以產生真實世界中之一或多個物件或類似此等物件之一靜態或移動影像(例如顯示在螢幕上)、一聲音資料信號(例如用作向一揚聲器之一輸入以產生一聲音信號)之資料，或控制用於經組態以在一真實世界環境中執行一導航及/或操控任務之任何形式的機電代理人(例如一機器人)之資料。舉例而言，資料處理任務可係藉由產生指示類別中之對應一或多者之輸出資料來將輸入資料分類成對應於輸入資料之內容之一或多個類別之一分類任務；或者資料處理任務可係產生表示資料輸入之語意內容之一聲音或影像之一任務；或者資料處理任務可係基於描述環境之感測器資料來產生控制資料之一任務。另一選擇係，資料處理任務可係將係自然語言之一編碼(例如一第一自然語言中之一文字)之一資料輸入轉換成係具有相同語意內容之自然語言之另一編碼(例如另一不同的自然語言中之一文字)之一資料輸出之一任務。因此，實例使獲得特定於該組一或多個硬體裝置之一經改良演算法成為可能，以執行資料處理任務之分量。
本說明書使用與系統及電腦程式組件有關的術語「經組態(configured)」。對於一或多個電腦之一系統，經組態以執行特定操作或動作意指該系統已經將在操作中致使系統執行操作或動作之軟體、韌體、硬體或其一組合安裝在該系統上。對於一或多個電腦程式，經組態以執行特定操作或動作意指一或多個程式包含在由資料處理設備執行時致使該設備執行操作或動作之指令。
本說明書中所描述之標的物及功能性操作之實施例可實施於包含本說明書中所揭露之結構及其結構等效物之數位電子電路系統、有形地體現之電腦軟體或韌體、電腦硬體中，或實施於其中之一或多者之組合中。可將本說明書中所描述之標的物之實施例實施為一或多個電腦程式，亦即，編碼於一有形非暫時性儲存媒體上供資料處理設備執行或用於控制資料處理設備之操作之一或多個電腦程式指令模組。電腦儲存媒體可係一機器可讀儲存裝置、一機器可讀儲存基板、一隨機或串列存取記憶體裝置，或者其中之一或多者之一組合。另一選擇係或另外，程式指令可編碼在一人為產生的傳播信號(例如，一機器產生的電、光或電磁信號)上，該信號經產生以編碼用於傳輸至適合的接收器設備以供由一資料處理設備執行之資訊。
術語「資料處理設備」係指資料處理硬體且涵蓋用於處理資料之所有類型的設備、裝置及機器，以實例之方式，包含一可程式化處理器、一電腦或者多個處理器或電腦。該設備亦可係或進一步包含特殊用途邏輯電路系統，例如一FPGA (場可程式化閘陣列)或一ASIC (特殊應用積體電路)。除硬體外，該設備視情況亦可包含為電腦程式建立一執行環境之程式碼，例如構成處理器韌體、一協議堆疊、一資料庫管理系統、一作業系統或其中之一或多者之組合之程式碼。
一電腦程式(亦可被稱為或描述為一程式、軟體、一軟體應用、一應用程式、一模組、一軟體模組、一指令碼或程式碼)可以任一形式的程式設計語言(包含編譯語言或解譯語言或者宣告語言或程序性語言)寫入；且該電腦程式可以任一形式部署，包含作為一獨立式程式或者作為一模組、分量、副常式或適用於一計算環境中之其他單元。一程式可以但不必須對應於一檔案系統中之一檔案。一程式可儲存於保持其他程式或資料(例如，儲存於一標記語言文件中之一或多個指令碼)之一文件之一部分中、儲存於專用於所討論之程式之一單個文件中或儲存於多個經協調文件(例如，儲存一或多個模組、子程式或程式碼之若干部分之文件)中。一電腦程式可經部署以在一個電腦上或位於一個位點處或跨越多個位點分佈且藉由一通信網路互連之多個電腦上執行。
在本說明書中，術語「引擎」廣泛地用於指代經程式化以執行一或多個特定功能之一基於軟體的系統、子系統或程序。大體而言，一引擎將實施為在一或多個位置中之一或多個電腦上安裝之一或多個軟體模組或組件。在某些情形下，一或多個電腦將專用於一特定引擎；在其他情形下，可在同一電腦或若干電腦上安裝及運行多個引擎。
本說明書中所描述之程序及邏輯流程可由執行一或多個電腦程式之一或多個可程式化電腦執行以藉由對輸入資料進行操作並產生輸出來執行功能。該等程序及邏輯流程亦可係藉由特殊用途邏輯電路系統(例如，一FPGA或一ASIC)或者藉由特殊用途邏輯電路系統及一或多個經程式化電腦之一組合執行。
適合於執行一電腦程式之電腦可係基於一般用途或特殊用途微處理器或者其兩者或者任一其他類型的中央處理單元。大體而言，一中央處理單元將自一唯讀記憶體或一隨機存取記憶體或其兩者接收指令及資料。一電腦之基本元件係用於執行指令之一中央處理單元以及用於儲存指令及資料之一或多個記憶體裝置。中央處理單元及記憶體可由特殊用途邏輯電路系統補充或併入於特殊用途邏輯電路系統中。大體而言，一電腦亦將包含用於儲存資料之一個或多個大容量儲存裝置(例如，磁碟、磁光碟或光碟)或以操作方式耦合以自該一或多個大容量儲存裝置接收資料或向其傳送資料或既接收又傳送資料。然而，一電腦不必須具有此類裝置。此外，一電腦可體現在另一裝置中，例如，一行動電話、一個人數位助理(PDA)、一行動音訊或視訊播放器、一遊戲主控台、一全球定位系統(GPS)接收器或一可攜式儲存裝置，例如一通用串列匯流排(USB)隨身碟，僅舉幾例。
適合於儲存電腦程式指令及資料之電腦可讀媒體包含所有形式之非揮發性記憶體、媒體及記憶體裝置，以實例之方式包含：半導體記憶體裝置(例如，EPROM、EEPROM及快閃記憶體裝置)；磁碟(例如，內部硬磁碟或可抽換式磁碟)；磁光碟；以及CD-ROM及DVD-ROM碟。
為提供與一使用者之互動，本說明書中所描述之標的物之實施例可實施於一電腦上，該電腦具有用於向使用者顯示資訊之一顯示裝置(例如，一CRT (陰極射線管)或LCD (液晶顯示器)監測器)，以及使用者可藉由其將輸入提供至電腦之一鍵盤及一指向裝置(例如，一滑鼠或一軌跡球)。亦可使用其他種類的裝置來提供與使用者之互動；舉例而言，提供給使用者之回饋可係任一形式的感觀回饋(例如，視覺回饋、聽覺回饋或觸覺回饋)；且來自使用者之輸入可以任何形式(包含聲音、語音或觸覺輸入)來接收。另外，一電腦可藉由向由使用者使用之一裝置發送文件及自該裝置接收文件而與一使用者互動；舉例而言，藉由回應於自一使用者裝置之一網頁瀏覽器接收到之請求而向該網頁瀏覽器發送網頁。此外，一電腦可藉由向一個人裝置(例如，正在運行一訊息接發應用程式之一智慧型電話)發送文字訊息或其他形式的訊息及作為回應自一使用者接收回應性訊息而與該使用者互動。
舉例而言，用於實施機器學習模型之資料處理設備亦可包含特殊用途硬體加速器單元，該等特殊用途硬體加速器單元用於處理機器學習訓練或產生之共同及運算密集部分，亦即，推理、工作負載。
可使用一機器學習框架(例如，一張量流程(TensorFlow)框架)實施及部署機器學習模型。
本說明書中所描述之標的物之實施例可實施於一計算系統中，該計算系統包含一後端組件(例如，作為一資料伺服器)或包含一中間體組件(例如，一應用伺服器)或包含一前端組件(例如，具有一使用者可透過其來與本說明書中所描述之標的物之一實施方案互動的一圖形使用者介面、一網頁瀏覽器或一應用程式之一用戶端電腦)或一或多個此類後端、中間體或前端組件之任一組合。該系統之組件可藉由任何數位資料通信形式或媒體(例如，一通信網路)來互連。通信網路之實例包含一區域網路(LAN)及一廣域網路(WAN) (例如網際網路)。
該計算系統可包含用戶端及伺服器。一用戶端與伺服器大體上彼此遠離且通常透過一通信網路互動。用戶端與伺服器之關係是藉助於在各別電腦上運行且彼此之間具有一用戶端-伺服器關係之電腦程式而產生。在某些實施方案中，一伺服器將資料(例如，一HTML頁面)傳輸至一使用者裝置(例如，出於向與充當一用戶端之一裝置互動之一使用者顯示資料及自該使用者接收使用者輸入之目的)。在使用者裝置處產生之資料(例如，使用者互動之一結果)可在伺服器處自該裝置接收。
雖然本說明書含有諸多特定實施方案細節，但此等細節不應解釋為對任何發明之範疇或對可主張之內容之範疇之限制，而是應解釋為可係特定發明之特定實施例特有之特徵之說明。在單獨實施例之內容脈絡中於本說明書中描述之特定特徵亦可以組合方式實施於一單個實施例中。相反地，在一單個實施例之內容脈絡中描述之各種特徵亦可單獨地或以任何適合子組合方式實施於多個實施例中。此外，儘管上文可將特徵描述為以特定組合形式起作用且甚至最初係如此主張，但在某些情形中，可自一所主張組合去除來自該組合之一或多個特徵，且所主張之組合可係針對於一子組合或一子組合之變化形式。
類似地，雖然以一特定次序在該等圖式中繪示及在申請專利範圍中陳述操作，但不應將此理解為需要以所展示之特定次序或以順序次序執行此等操作或執行所有所圖解說明之操作以達成合意的結果。在特定情形下，多任務及並行處理可係有利的。此外，不應將在上文所描述之實施例中之各種系統模組及組件之分離理解為在所有實施例中需要此分離，且應理解，大體上可將所描述之程式組件及系統一起整合於一單個軟體產品中或封裝至多個軟體產品中。
已描述標的物之特定實施例。在隨附申請專利範圍之範疇內存在其他實施例。舉例而言，申請專利範圍中所引用的動作可以一不同次序來執行且仍達成合意的結果。另外，附圖中所描述之程序未必需要所展示之特定次序或順序次序來達成合意的結果。在某些情形下，多任務及並行處理可係有利的。
100:最佳化系統/系統 100A:分解引擎 100B:訓練引擎 102a-102n:狀態 104a-104c:樹狀搜尋 106:張量分解/分解/經改良張量分解 108:候選演算法 110:基準測試得分 112a:訓練實例 112b:合成訓練實例 114:訓練資料儲存裝置/資料儲存裝置 118:訓練張量狀態/訓練狀態 120:網路參數 200:程序 202:步驟 204:步驟 206:步驟 208:步驟 210:步驟 212:步驟 300:程序 302:步驟 304:步驟 306:步驟 308:步驟 310:步驟 312:步驟 400:程序 402:步驟 404:步驟 406:步驟 408:步驟 410:步驟 412:步驟 500:程序 502:步驟 504:步驟 506:步驟 508:步驟 a 1-a t:動作 S 0:初始狀態 S:狀態/訓練張量狀態/訓練狀態 S t:狀態
圖1展示一實例最佳化系統。
圖2係用於產生一張量分解之一實例程序之一流程圖。
圖3係用於執行一樹狀搜尋之一實例程序之一流程圖。
圖4係用於自張量分解產生訓練實例之一實例程序之一流程圖。
圖5係用於更新一神經網路之網路參數值之一實例程序之一流程圖。
圖6係由一張量分解參數化之一矩陣乘法演算法之一實例。
圖7A至圖7C係展示針對各種硬體裝置最佳化之矩陣乘法演算法之實驗資料。
在各個圖式中，相同元件符號及名稱指示相同元件。
100:最佳化系統/系統
100A:分解引擎
100B:訓練引擎
102a-102n:狀態
104a-104c:樹狀搜尋
106:張量分解/分解/經改良張量分解
108:候選演算法
110:基準測試得分
112a:訓練實例
112b:合成訓練實例
114:訓練資料儲存裝置/資料儲存裝置
118:訓練張量狀態/訓練狀態
120:網路參數
a1-at:動作
S0:初始狀態
S:狀態/訓練張量狀態/訓練狀態
St:狀態

Claims (20)

  1. 一種由一或多個電腦執行之用於獲得一經最佳化演算法之方法，該經最佳化演算法(i)功能上等效於一目標演算法且(ii)當在一目標組的一或多個硬體裝置上執行時最佳化一或多個目標性質，該方法包括： 初始化表示該目標演算法之一目標張量； 使用具有複數個網路參數之一神經網路來產生該目標張量之一張量分解，該張量分解對一候選演算法進行參數化，其中該神經網路經組態以接收一張量之一狀態作為輸入且根據該等網路參數處理該輸入以產生包括用於對該張量應用修改之一策略之一網路輸出，且其中產生該張量分解包括： 針對一步驟序列中之每一步驟： 獲得該目標張量之一當前狀態； 藉由自表示該當前狀態之一根節點開始執行具有表示該目標張量之狀態之若干節點之一狀態樹的一樹狀搜尋來判定針對該當前狀態之一目標網路輸出，其中該樹狀搜尋係由該神經網路根據該等網路參數引導的； 使用針對該當前狀態之該目標網路輸出來向該目標張量應用一修改；及 至少部分地基於在應用該修改之後該目標張量是否等於一零張量來判定是否終止該序列；以及 在該步驟序列中之每一步驟處自應用於該目標張量之該等修改產生該張量分解； 當在該目標組的硬體裝置上執行該候選演算法時，針對該等目標性質中之每一者產生目標性質值； 基於該候選演算法之該等目標性質值來判定針對該張量分解之一基準測試得分； 自該張量分解及該基準測試得分產生一訓練實例；以及 將該訓練實例儲存在一訓練資料儲存裝置中以供用於更新該神經網路之該等網路參數。
  2. 如請求項1之方法，其進一步包括： 選擇一特定候選演算法作為該經最佳化演算法，該特定候選演算法係藉由使用基於針對該特定候選演算法之一基準測試得分之該神經網路產生的。
  3. 如請求項1或2之方法，其中該策略定義對將自該張量減去之可能的秩一項之一機率分佈。
  4. 如請求項1或2之方法，其中該網路輸出進一步包括一返回輸出，該返回輸出定義由處於該狀態中之該張量產生之一經估計返回。
  5. 如請求項4之方法，其中該經估計返回係一張量分解之一預期基準測試得分之一估計。
  6. 如請求項4之方法，其中該經估計返回係一張量分解之一預期秩之一估計。
  7. 如請求項4之方法，其中執行該樹狀搜尋包括： 基於被指派給連接該狀態樹之節點之邊之動作得分而遍歷該等邊直至到達一葉節點，其中邊表示待應用於該目標張量之可能的修改； 使用該神經網路根據該等網路參數來處理由該葉節點表示之該目標張量之一狀態以針對該葉節點產生一網路輸出； 使用針對該葉節點之一策略在該葉節點處擴展該狀態樹；及 針對該狀態樹之已被遍歷之每一邊： 增量該邊之一訪問計數；及 基於根據針對該葉節點之一返回輸出建構之一值來更新針對該邊之一動作得分。
  8. 如請求項7之方法，其中執行該樹狀搜尋進一步包括： 在一換位表中儲存在該樹狀搜尋期間遇到的一或多個節點； 當遍歷邊時，判定一新遇到的節點表示與儲存在該換位表中之一先前遇到的節點相同的該目標張量之一狀態；及 作為回應，將該新遇到的節點與該先前遇到的節點換位。
  9. 如請求項7之方法，其中判定來自該樹狀搜尋之該目標網路輸出進一步包括： 若該根節點之所有邊之一總訪問計數大於一最大總訪問計數，則使用一自適應溫度方案來平滑化該根節點之邊之訪問計數。
  10. 如請求項7之方法，其中判定來自該樹狀搜尋之該目標網路輸出進一步包括： 忽略該根節點的具有比該根節點的具有一最高訪問計數之一邊之一動作得分低的動作得分之邊。
  11. 如請求項1或2之方法，其中初始化該目標張量包括對該目標張量執行基的一改變，且其中產生該張量分解包括對該張量分解執行基的一逆向改變。
  12. 如請求項1或2之方法，其進一步包括： 產生一或多個合成張量之一組張量分解，其中一合成張量係一經隨機初始化的張量； 自合成張量之該組張量分解產生一組合成訓練實例；及 將該組合成訓練實例儲存在該訓練資料儲存裝置中以供用於更新該神經網路之該等網路參數。
  13. 如請求項1或2之方法，其進一步包括： 自該訓練資料儲存裝置擷取與一訓練目標相關聯的一張量之一訓練狀態； 使用該神經網路根據該等網路參數處理該訓練狀態以產生一訓練網路輸出； 判定一目標函數相對於該等網路參數之一梯度，該目標函數鼓勵該訓練網路輸出達到針對該訓練狀態之該訓練目標；及 根據該梯度來更新該等網路參數。
  14. 如請求項1或2之方法，其中該經最佳化演算法係在該目標組的硬體裝置上遞歸地執行。
  15. 如請求項1或2之方法，其中該目標演算法計算一雙線性映射。
  16. 如請求項15之方法，其中該雙線性映射係矩陣乘法。
  17. 如請求項1或2之方法，其中該等目標性質包括以下各項中之至少一者： 該經最佳化演算法之運算複雜度， 該目標組的硬體裝置在執行該經最佳化演算法時之運行時間， 該目標組的硬體裝置在執行該經最佳化演算法時之快取效能， 該經最佳化演算法在該目標組的硬體裝置上被執行時之參考區域性，或 該目標組的硬體裝置在執行該經最佳化演算法時之功率消耗。
  18. 如請求項1或2之方法，其中該目標組的硬體裝置係一組硬體裝置之一模擬。
  19. 如請求項1或2之方法，其中該目標組的硬體裝置包括以下各項中之至少一者：一中央處理單元(CPU)、一圖形處理單元(GPU)、一張量處理單元(TPU)或一特殊應用積體電路(ASIC)。
  20. 如請求項1或2之方法，其進一步包括： 接收一新輸入；及 藉由在該目標組的硬體裝置上執行該經最佳化演算法而對該新輸入執行該目標演算法。
TW112137899A 2022-10-03 2023-10-03 最佳化用於硬體裝置之演算法 TWI851438B (zh)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US17/959,210 US20240127045A1 (en) 2022-10-03 2022-10-03 Optimizing algorithms for hardware devices
US17/959,210 2022-10-03

Publications (2)

Publication Number Publication Date
TW202429333A true TW202429333A (zh) 2024-07-16
TWI851438B TWI851438B (zh) 2024-08-01

Family

ID=88290878

Family Applications (2)

Application Number Title Priority Date Filing Date
TW112137899A TWI851438B (zh) 2022-10-03 2023-10-03 最佳化用於硬體裝置之演算法
TW113129006A TW202447462A (zh) 2022-10-03 2023-10-03 最佳化用於硬體裝置之演算法

Family Applications After (1)

Application Number Title Priority Date Filing Date
TW113129006A TW202447462A (zh) 2022-10-03 2023-10-03 最佳化用於硬體裝置之演算法

Country Status (3)

Country Link
US (1) US20240127045A1 (zh)
TW (2) TWI851438B (zh)
WO (1) WO2024074452A1 (zh)

Families Citing this family (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN118798858B (zh) * 2024-09-13 2025-02-07 杭州市北京航空航天大学国际创新研究院(北京航空航天大学国际创新学院) 一种基于ac-mcts算法的面向集群系统灾后修复性维修的方法

Family Cites Families (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN109815339B (zh) * 2019-01-02 2022-02-08 平安科技（深圳）有限公司 基于TextCNN知识抽取方法、装置、计算机设备及存储介质
CA3069209A1 (en) * 2019-01-23 2020-07-23 Royal Bank Of Canada System and method for tree-based machine learning
WO2021116404A1 (en) * 2019-12-11 2021-06-17 Inait Sa Constructing and operating an artificial recurrent neural network
TWI761834B (zh) * 2020-05-14 2022-04-21 治略資訊整合股份有限公司 感測數據智能檢測方法與系統
US11580042B2 (en) * 2020-11-30 2023-02-14 Seagate Technology Llc Automated and intelligent data channel optimizers with sensitivity assessment
US12166688B2 (en) * 2020-12-24 2024-12-10 Intel Corporation Methods, systems, articles of manufacture and apparatus to optimize resources in edge networks
US11975451B2 (en) * 2021-03-27 2024-05-07 Mitsubishi Electric Research Laboratories, Inc. Simulation-in-the-loop tuning of robot parameters for system modeling and control

Also Published As

Publication number Publication date
WO2024074452A1 (en) 2024-04-11
TW202447462A (zh) 2024-12-01
US20240127045A1 (en) 2024-04-18
TWI851438B (zh) 2024-08-01

Similar Documents

Publication Publication Date Title
JP7413580B2 (ja) ニューラルネットワークを使用した集積回路フロアプランの生成
CN113128702B (zh) 一种基于强化学习的神经网络自适应分布式并行训练方法
JP7157154B2 (ja) 性能予測ニューラルネットワークを使用したニューラルアーキテクチャ探索
Xu et al. Learning to explore via meta-policy gradient
CN110503192A (zh) 资源有效的神经架构
EP3938963A1 (en) Scheduling computation graphs using neural networks
US11651260B2 (en) Hardware-based machine learning acceleration
KR20190113928A (ko) 강화 학습을 통한 디바이스 배치 최적화
CN110383298A (zh) 用于连续控制任务的数据高效强化学习
CN109313720A (zh) 具有稀疏访问的外部存储器的增强神经网络
CN113919482A (zh) 智能体训练方法、装置、计算机设备和存储介质
Liu et al. AdaDeep: A usage-driven, automated deep model compression framework for enabling ubiquitous intelligent mobiles
US20240202511A1 (en) Gated linear networks
JP2023544175A (ja) メッシュ表現およびグラフニューラルネットワークを使用した物理的環境のシミュレーション
CN110235149A (zh) 神经情节控制
TWI851438B (zh) 最佳化用於硬體裝置之演算法
TW202244792A (zh) 產生及全域地調諧應用程式特定之機器學習加速器
EP4006788B1 (en) Quantum circuit determining method and apparatus, device, and storage medium
JP2024504179A (ja) 人工知能推論モデルを軽量化する方法およびシステム
Zhou et al. Hierarchical surrogate-assisted evolutionary optimization framework
Kaedi et al. Biasing Bayesian optimization algorithm using case based reasoning
He et al. Gradient-based optimization for quantum architecture search
Anis FPGA implementation of parallel particle swarm optimization algorithm and compared with genetic algorithm
CN118710754A (zh) 基于扩散概率模型的文生图方法、装置、设备及存储介质
JP7552996B2 (ja) ハイパーパラメータチューニング方法、プログラム、ユーザプログラム、装置、方法