張量計算從愛因斯坦時代起就是科學(xué)研究的重要內(nèi)容。大數(shù)據(jù)時代，大數(shù)據(jù)和機器學(xué)習(xí)對稀疏張量（絕大多數(shù)元素為 0 的稀疏數(shù)組）的計算要求越來越高。
近日，MIT 的一款新系統(tǒng)可以自動生成針對稀疏張量計算等操作的代碼，比當(dāng)前常用的軟件包快 100 倍，被譽為“近年來在編譯優(yōu)化領(lǐng)域令人激動的進步之一”。
我們生活在一個大數(shù)據(jù)的時代，但是絕大多數(shù)的數(shù)據(jù)都是“稀疏的”。想象一下，比如說，一個超大規(guī)模的表格，它存儲著所有的亞馬遜的顧客和所有商品的對應(yīng)信息，如果一個顧客購買了某樣商品，就存儲一個“1”，否則為"0”。那么這個表格的絕大部分?jǐn)?shù)據(jù)都會是 0。
面對這樣稀疏的數(shù)據(jù)，分析算法終要做大量有 0 參與的加法和乘法，這是對計算資源的一種浪費。
程序員可以通過編寫特定的代碼來躲開零實體來規(guī)避這樣的問題，但是那樣的代碼是復(fù)雜的，而且只對非常有限的問題有效。
在 ACM 的 SPLASH（Systems, Programming, Languages and Applications: Software for Humanity）會議上，來自 MIT、法國的替代能源和原子能委員會和 Adobe Research 的研究者近推出了一個新的系統(tǒng)，它可以自動產(chǎn)生針對稀疏數(shù)據(jù)的優(yōu)化的代碼。
這樣的代碼比現(xiàn)存的未優(yōu)化的軟件包快 100 倍。而且其性能可以與那些為特定稀疏數(shù)據(jù)操作而手動精心優(yōu)化過的代碼相媲美，卻只需要程序編寫者做極少的工作。
這個用于稀疏代數(shù)編譯器的系統(tǒng)叫做Taco。根據(jù)計算機科學(xué)界的說法，一個像上文提到的，亞馬遜表格那樣的數(shù)據(jù)結(jié)構(gòu)稱作矩陣，而一個張量僅僅是一個更高維的類似的東西。如果前面提到的亞馬遜的表格也保存著客戶、對應(yīng)的商品、客戶對商品的評級以及評論中使用到的詞語，那么它將會是一個四維的張量。
“稀疏表示已經(jīng)存在了超過 60 年”，MIT 電氣工程與計算科學(xué)的教授，新論文的主要作者 Saman Amarasinghe 說道，“但是沒有人知道如何為它們自動生成代碼。人們想到一些非常具體的操作——稀疏矩陣與向量相乘，稀疏矩陣與向量相乘再加上一個向量，稀疏矩陣與稀疏矩陣相乘，稀疏矩陣與稀疏矩陣相乘再與稀疏矩陣相乘。我們所做的大的貢獻就是實現(xiàn)了，當(dāng)矩陣是稀疏的時候，可以為任何張量代數(shù)表達式自動生成代碼的能力。”
自定義核
近年來，對張量的數(shù)學(xué)操作——張量代數(shù)——對大數(shù)據(jù)分析和機器學(xué)習(xí)都變得至關(guān)重要。其實，從愛因斯坦時代起，它就成為科學(xué)研究中至關(guān)重要的部分。
在此之前，為了解決張量代數(shù)問題，數(shù)學(xué)軟件已經(jīng)將張量操作分解成它們的組成部分。比如說，如果一個計算需要將兩個張量相乘然后再與第三個相加，軟件將會在前兩個張量上執(zhí)行標(biāo)準(zhǔn)張量乘法操作，存儲結(jié)果，然后執(zhí)行標(biāo)準(zhǔn)張量相加操作。
然而，在大數(shù)據(jù)時代，這個方法太費時間了。Kjolstad 解釋道，為了在數(shù)量龐大的數(shù)據(jù)集上執(zhí)行高效的操作，張量的每個序列都需要它自己的“核”，或者說是計算模板。
“如果你在一個核中操作，你就能把所有操作一次完成，并且你可以讓它執(zhí)行的更快一點，而不需要先將結(jié)果保存到內(nèi)存中然后再把它讀回來以便和其他的東西相加”。Kjolstad 說，“你可以在一個循環(huán)中完成它。”
計算機科學(xué)的研究者已經(jīng)研制出針對機器學(xué)習(xí)和大數(shù)據(jù)分析中常見張量操作的核，比如說上文中 Amarasinghe 列舉的。但是這些可能需要的核的數(shù)量是無限的：比如說，將三個張量相加的核和將四個張量相加的核是不一樣的。而將三個三維張量相加的核和將三個四維張量相加的核也是不一樣的。
許多張量操作包括將來自一個張量的一個實體和來自另一個張量的一個實體相乘的操作。如果這兩個實體都是 0，那么他們的結(jié)果也是 0。而操縱龐大而稀疏的矩陣的程序就會浪費大量的時間來對 0 進行加和乘操作。
為稀疏張量手動優(yōu)化的代碼識別出零實體并精簡包含他們的操作——在加法中只關(guān)注非零的實體并完全省略零實體參與的乘法。這使得張量操作更快，但是需要程序編寫者做大量的工作。
比如說，將兩個矩陣相乘的代碼，如果矩陣是稠密的（沒有實體可以被省略）可能只有 12 行。但是如果矩陣是稀松的，相同的操作可能需要 100 行或者更多的代碼來去處理應(yīng)該被省略的部分。
引入 Taco
Taco 完全自動地添加額外的代碼。編程者只需要指定張量的大小，是稀疏的還是稠密的，以及存儲它的值的文件即可。對任何針對兩個張量的操作，Taco 建立一個分層的映射地圖指出，首先，兩個張量哪一對相對的實體是非零的，其次，兩個張量中哪個實體和零配對。而所有 0 與 0 的配對將被直接遺棄。
Taco 也使用一個高效的索引方案去存儲稀疏張量的非零值。如果包含 0 值，一個亞馬遜公開發(fā)布的，存儲客戶 ID、對應(yīng)購買物品和從評論中提取的描述詞語的張量，會占用 107 億字節(jié)的數(shù)據(jù)，或者大說，約是估計出的的所有的谷歌服務(wù)器存儲容量 10 倍。而使用 Taco 的壓縮方案，它只占用 13 千兆字節(jié)，用一個智能手機就足夠存儲。
“在過去的二十年中，許多研究小組一直在嘗試解決稀疏矩陣的編譯優(yōu)化和代碼自動生成問題，但是收效甚微。”俄亥俄州立大學(xué)計算機科學(xué)和工程的教授 Saday Sadayappan 說道，“近 Fred 和 Saman 取得的進展代表著在這一長期存在的問題上根本性的突破”，他并沒有參與這項工作。
“他們的編譯器通過自動生成高效的代碼，現(xiàn)在已經(jīng)可以讓應(yīng)用程序的開發(fā)者用非常簡單，方便的高級符號來指定復(fù)雜的稀疏矩陣和張量計算”。他繼續(xù)說道，“對一些稀疏計算，編譯器生成的代碼已經(jīng)和手動精心改進的一樣好甚至更好。它有望成為真正的游戲規(guī)則改變者，它是近年來在編譯優(yōu)化領(lǐng)域令人激動的進步之一。”