[發(fā)明專利]應(yīng)用于數(shù)據(jù)壓縮與分析的張量分解性能優(yōu)化方法和系統(tǒng)

在審

• 申請(qǐng)?zhí)枺?/td>: 202310181406.3
• 申請(qǐng)日: 2023-02-20
• 公開（公告）號(hào): CN116401503A
• 公開（公告）日: 2023-07-07
• 發(fā)明（設(shè)計(jì)）人: 楊超;李敏;肖傳福;丁明朔;陳暢
• 申請(qǐng)（專利權(quán)）人: 北京大學(xué);北京大學(xué)長(zhǎng)沙計(jì)算與數(shù)字經(jīng)濟(jì)研究院
• 主分類號(hào): G06F17/16
• 分類號(hào): G06F17/16;G06F18/2135;G06F16/901
• 代理公司: 北京冠和權(quán)律師事務(wù)所 11399
• 代理人: 鄭延斌

本發(fā)明提出了應(yīng)用于數(shù)據(jù)壓縮與分析的張量分解性能優(yōu)化方法和系統(tǒng)。所述張量分解算法的主要性能瓶頸是連續(xù)的張量矩陣乘運(yùn)算，本發(fā)明性能優(yōu)化方法將張量分解過程建模成樹的形式，通過盡量重用操作，從而減少關(guān)鍵操作的計(jì)算量，提升計(jì)算性能。具體包括：樹的構(gòu)建：首先，將要壓縮的N階輸入數(shù)據(jù)張量χ作為根節(jié)點(diǎn)，并將N個(gè)數(shù)據(jù)子節(jié)點(diǎn)與根節(jié)點(diǎn)相連，其中，一個(gè)數(shù)據(jù)節(jié)點(diǎn)對(duì)應(yīng)一顆子樹；以分治的方式對(duì)每顆子樹進(jìn)行結(jié)構(gòu)創(chuàng)建。計(jì)算過程：從根節(jié)點(diǎn)，以深度優(yōu)先方式遍歷樹，每遍歷到一個(gè)節(jié)點(diǎn)，進(jìn)行一次張量矩陣乘操作計(jì)算，最終完成全部運(yùn)算。該優(yōu)化方法可以大幅減少張量矩陣乘操作的次數(shù)，從而提升計(jì)算性能。

技術(shù)領(lǐng)域

本發(fā)明提出了應(yīng)用于數(shù)據(jù)壓縮與分析的張量分解性能優(yōu)化方法和系統(tǒng)，屬于數(shù)據(jù)壓縮技術(shù)領(lǐng)域。

背景技術(shù)

Tucker分解是張量計(jì)算中最常用的分解形式之一，被廣泛應(yīng)用于數(shù)據(jù)分析、科學(xué)計(jì)算、人工智能等領(lǐng)域。Tucker分解將一個(gè)規(guī)模為I₁×I₂×......×I_N的張量χ，分解成：χ≈g×₁U⁽¹⁾×₂U⁽²⁾......_NU^(N)的形式，其中，g是核張量，其規(guī)模為R₁×R₂×......×R_N，U⁽ⁿ⁾為因子矩陣(n＝1，2，...,N)，其規(guī)模為且一般滿足列正交性。HOOI(高階正交迭代)算法是Tucker分解最常用的方法之一，其是一種迭代算法，如圖1所示。HOOI算法包括兩層循環(huán)有兩層：外層循環(huán)(第2-9行)控制算法的收斂，一般地，循環(huán)終止準(zhǔn)則是固定迭代次數(shù)上限或者相鄰兩步誤差低于指定水平；在每個(gè)外循環(huán)內(nèi)部，會(huì)對(duì)張量的每個(gè)mode進(jìn)行循環(huán)(第3-8行)，每次循環(huán)包括TTMc計(jì)算模塊(第5行)和因子矩陣更新模塊(第7-8行)。其中TTMc計(jì)算模塊是HOOI算法最耗時(shí)的部分，該計(jì)算模塊由一系列連續(xù)的TTM(張量矩陣乘)運(yùn)算組成。

針對(duì)TTMc計(jì)算模塊，涌現(xiàn)了一些高性能的計(jì)算優(yōu)化工作。對(duì)直接計(jì)算方法來說，它沒有利用HOOI算法的特點(diǎn)，對(duì)所有TTM操作進(jìn)行重新計(jì)算，具有比較差的性能；在直接計(jì)算方法之上，balanced-tree方法在內(nèi)迭代范圍內(nèi)展開重用，盡可能重用了不同迭代步間的TTM結(jié)果，減少TTM操作的計(jì)算次數(shù)，提升了一些性能。但是balanced-tree方法同樣存在壓縮效率和壓縮性能較差的問題。

發(fā)明內(nèi)容

本發(fā)明提供了應(yīng)用于數(shù)據(jù)壓縮與分析的張量分解性能優(yōu)化方法和系統(tǒng)，用以解決現(xiàn)有數(shù)據(jù)壓縮過程中壓縮效率和壓縮性能較差的問題，所采取的技術(shù)方案如下：

應(yīng)用于數(shù)據(jù)壓縮與分析的張量分解性能優(yōu)化方法，所述張量分解性能優(yōu)化方法包括：

將要壓縮的N階輸入數(shù)據(jù)張量作為根節(jié)點(diǎn)，并將N個(gè)數(shù)據(jù)子節(jié)點(diǎn)與根節(jié)點(diǎn)相連，其中，一個(gè)數(shù)據(jù)子節(jié)點(diǎn)對(duì)應(yīng)一顆子樹；

以分治的方式對(duì)每顆子樹進(jìn)行結(jié)構(gòu)創(chuàng)建；

從根節(jié)點(diǎn)，以深度優(yōu)先方式遍歷樹，完成對(duì)應(yīng)的連續(xù)張量矩陣乘計(jì)算。

進(jìn)一步地，每顆子樹的根節(jié)點(diǎn)的標(biāo)記號(hào)為i，其中，i的取值范圍為i∈[1，N]。

進(jìn)一步地，以分治的方式對(duì)每顆子樹進(jìn)行結(jié)構(gòu)創(chuàng)建，包括：

將數(shù)據(jù)子節(jié)點(diǎn)對(duì)應(yīng)的除了i以外的標(biāo)號(hào)進(jìn)行提取，形成標(biāo)號(hào)集合A＝{j,j∈[1，N]，j≠i}；

將標(biāo)號(hào)集合A中的標(biāo)號(hào)分成兩組：A1＝{1,2,...,m}，A2＝{m+1,...,N}；

判斷A1中包含的節(jié)點(diǎn)個(gè)數(shù)m是否為1，如果m為1，則直接將A1中的節(jié)點(diǎn)掛在i節(jié)點(diǎn)上；如果m不為1，則將A1中的標(biāo)號(hào)按照預(yù)設(shè)連續(xù)原則形成m個(gè)連續(xù)節(jié)點(diǎn)串，并按照所述預(yù)設(shè)連續(xù)原則在所述m個(gè)連續(xù)節(jié)點(diǎn)串中提取首節(jié)點(diǎn)，將所述首節(jié)點(diǎn)掛在i節(jié)點(diǎn)上；