張量計(jì)算從愛(ài)因斯坦時(shí)代起就是科學(xué)研究的重要內(nèi)容。大數(shù)據(jù)時(shí)代，大數(shù)據(jù)和機(jī)器學(xué)習(xí)對(duì)稀疏張量（絕大多數(shù)元素為 0 的稀疏數(shù)組）的計(jì)算要求越來(lái)越高。

近日，MIT 的一款新系統(tǒng)可以自動(dòng)生成針對(duì)稀疏張量計(jì)算等操作的代碼，比當(dāng)前常用的軟件包快 100 倍，被譽(yù)為“近年來(lái)在編譯優(yōu)化領(lǐng)域最令人激動(dòng)的進(jìn)步之一”。

我們生活在一個(gè)大數(shù)據(jù)的時(shí)代，但是絕大多數(shù)的數(shù)據(jù)都是“稀疏的”。想象一下，比如說(shuō)，一個(gè)超大規(guī)模的表格，它存儲(chǔ)著所有的亞馬遜的顧客和所有商品的對(duì)應(yīng)信息，如果一個(gè)顧客購(gòu)買(mǎi)了某樣商品，就存儲(chǔ)一個(gè)“1”，否則為“0”。那么這個(gè)表格的絕大部分?jǐn)?shù)據(jù)都會(huì)是 0。

面對(duì)這樣稀疏的數(shù)據(jù)，分析算法最終要做大量有 0 參與的加法和乘法，這是對(duì)計(jì)算資源的一種浪費(fèi)。

程序員可以通過(guò)編寫(xiě)特定的代碼來(lái)躲開(kāi)零實(shí)體來(lái)規(guī)避這樣的問(wèn)題，但是那樣的代碼是復(fù)雜的，而且只對(duì)非常有限的問(wèn)題有效。

在 ACM 的 SPLASH（Systems, Programming, Languages and Applications: Software for Humanity）會(huì)議上，來(lái)自 MIT、法國(guó)的替代能源和原子能委員會(huì)和 Adobe Research 的研究者最近推出了一個(gè)新的系統(tǒng)，它可以自動(dòng)產(chǎn)生針對(duì)稀疏數(shù)據(jù)的優(yōu)化的代碼。

這樣的代碼比現(xiàn)存的未優(yōu)化的軟件包快 100 倍。而且其性能可以與那些為特定稀疏數(shù)據(jù)操作而手動(dòng)精心優(yōu)化過(guò)的代碼相媲美，卻只需要程序編寫(xiě)者做極少的工作。

這個(gè)用于稀疏代數(shù)編譯器的系統(tǒng)叫做Taco。根據(jù)計(jì)算機(jī)科學(xué)界的說(shuō)法，一個(gè)像上文提到的，亞馬遜表格那樣的數(shù)據(jù)結(jié)構(gòu)稱作矩陣，而一個(gè)張量?jī)H僅是一個(gè)更高維的類(lèi)似的東西。如果前面提到的亞馬遜的表格也保存著客戶、對(duì)應(yīng)的商品、客戶對(duì)商品的評(píng)級(jí)以及評(píng)論中使用到的詞語(yǔ)，那么它將會(huì)是一個(gè)四維的張量。

“稀疏表示已經(jīng)存在了超過(guò) 60 年”，MIT 電氣工程與計(jì)算科學(xué)的教授，新論文的主要作者 Saman Amarasinghe 說(shuō)道，“但是沒(méi)有人知道如何為它們自動(dòng)生成代碼。人們想到一些非常具體的操作——稀疏矩陣與向量相乘，稀疏矩陣與向量相乘再加上一個(gè)向量，稀疏矩陣與稀疏矩陣相乘，稀疏矩陣與稀疏矩陣相乘再與稀疏矩陣相乘。我們所做的***的貢獻(xiàn)就是實(shí)現(xiàn)了，當(dāng)矩陣是稀疏的時(shí)候，可以為任何張量代數(shù)表達(dá)式自動(dòng)生成代碼的能力。”

自定義核

近年來(lái)，對(duì)張量的數(shù)學(xué)操作——張量代數(shù)——對(duì)大數(shù)據(jù)分析和機(jī)器學(xué)習(xí)都變得至關(guān)重要。其實(shí)，從愛(ài)因斯坦時(shí)代起，它就成為科學(xué)研究中至關(guān)重要的部分。

在此之前，為了解決張量代數(shù)問(wèn)題，數(shù)學(xué)軟件已經(jīng)將張量操作分解成它們的組成部分。比如說(shuō)，如果一個(gè)計(jì)算需要將兩個(gè)張量相乘然后再與第三個(gè)相加，軟件將會(huì)在前兩個(gè)張量上執(zhí)行標(biāo)準(zhǔn)張量乘法操作，存儲(chǔ)結(jié)果，然后執(zhí)行標(biāo)準(zhǔn)張量相加操作。

然而，在大數(shù)據(jù)時(shí)代，這個(gè)方法太費(fèi)時(shí)間了。Kjolstad 解釋道，為了在數(shù)量龐大的數(shù)據(jù)集上執(zhí)行高效的操作，張量的每個(gè)序列都需要它自己的“核”，或者說(shuō)是計(jì)算模板。

“如果你在一個(gè)核中操作，你就能把所有操作一次完成，并且你可以讓它執(zhí)行的更快一點(diǎn)，而不需要先將結(jié)果保存到內(nèi)存中然后再把它讀回來(lái)以便和其他的東西相加”。Kjolstad 說(shuō)，“你可以在一個(gè)循環(huán)中完成它。”

計(jì)算機(jī)科學(xué)的研究者已經(jīng)研制出針對(duì)機(jī)器學(xué)習(xí)和大數(shù)據(jù)分析中常見(jiàn)張量操作的核，比如說(shuō)上文中 Amarasinghe 列舉的。但是這些可能需要的核的數(shù)量是***的：比如說(shuō)，將三個(gè)張量相加的核和將四個(gè)張量相加的核是不一樣的。而將三個(gè)三維張量相加的核和將三個(gè)四維張量相加的核也是不一樣的。

許多張量操作包括將來(lái)自一個(gè)張量的一個(gè)實(shí)體和來(lái)自另一個(gè)張量的一個(gè)實(shí)體相乘的操作。如果這兩個(gè)實(shí)體都是 0，那么他們的結(jié)果也是 0。而操縱龐大而稀疏的矩陣的程序就會(huì)浪費(fèi)大量的時(shí)間來(lái)對(duì) 0 進(jìn)行加和乘操作。

為稀疏張量手動(dòng)優(yōu)化的代碼識(shí)別出零實(shí)體并精簡(jiǎn)包含他們的操作——在加法中只關(guān)注非零的實(shí)體并完全省略零實(shí)體參與的乘法。這使得張量操作更快，但是需要程序編寫(xiě)者做大量的工作。

比如說(shuō)，將兩個(gè)矩陣相乘的代碼，如果矩陣是稠密的（沒(méi)有實(shí)體可以被省略）可能只有 12 行。但是如果矩陣是稀松的，相同的操作可能需要 100 行或者更多的代碼來(lái)去處理應(yīng)該被省略的部分。

引入 Taco

Taco 完全自動(dòng)地添加額外的代碼。編程者只需要指定張量的大小，是稀疏的還是稠密的，以及存儲(chǔ)它的值的文件即可。對(duì)任何針對(duì)兩個(gè)張量的操作，Taco 建立一個(gè)分層的映射地圖指出，首先，兩個(gè)張量哪一對(duì)相對(duì)的實(shí)體是非零的，其次，兩個(gè)張量中哪個(gè)實(shí)體和零配對(duì)。而所有 0 與 0 的配對(duì)將被直接遺棄。

Taco 也使用一個(gè)高效的索引方案去存儲(chǔ)稀疏張量的非零值。如果包含 0 值，一個(gè)亞馬遜公開(kāi)發(fā)布的，存儲(chǔ)客戶 ID、對(duì)應(yīng)購(gòu)買(mǎi)物品和從評(píng)論中提取的描述詞語(yǔ)的張量，會(huì)占用 107 億字節(jié)的數(shù)據(jù)，或者大說(shuō)，約是估計(jì)出的的所有的谷歌服務(wù)器存儲(chǔ)容量 10 倍。而使用 Taco 的壓縮方案，它只占用 13 千兆字節(jié)，用一個(gè)智能手機(jī)就足夠存儲(chǔ)。

“在過(guò)去的二十年中，許多研究小組一直在嘗試解決稀疏矩陣的編譯優(yōu)化和代碼自動(dòng)生成問(wèn)題，但是收效甚微。”俄亥俄州立大學(xué)計(jì)算機(jī)科學(xué)和工程的教授 Saday Sadayappan 說(shuō)道，“最近 Fred 和 Saman 取得的進(jìn)展代表著在這一長(zhǎng)期存在的問(wèn)題上根本性的突破”，他并沒(méi)有參與這項(xiàng)工作。

“他們的編譯器通過(guò)自動(dòng)生成高效的代碼，現(xiàn)在已經(jīng)可以讓?xiě)?yīng)用程序的開(kāi)發(fā)者用非常簡(jiǎn)單，方便的高級(jí)符號(hào)來(lái)指定復(fù)雜的稀疏矩陣和張量計(jì)算”。他繼續(xù)說(shuō)道，“對(duì)一些稀疏計(jì)算，編譯器生成的代碼已經(jīng)和手動(dòng)精心改進(jìn)的一樣好甚至更好。它有望成為真正的游戲規(guī)則改變者，它是近年來(lái)在編譯優(yōu)化領(lǐng)域最令人激動(dòng)的進(jìn)步之一。”

轉(zhuǎn)載自：DeepTech深科技 網(wǎng)易號(hào)