張量計算從愛因斯坦時代起就是科學研究的重要內容。大數據時代，大數據和機器學習對稀疏張量（絕大多數元素為 0 的稀疏數組）的計算要求越來越高。

近日，MIT 的一款新系統可以自動生成針對稀疏張量計算等操作的代碼，比當前常用的軟件包快 100 倍，被譽為“近年來在編譯優化領域最令人激動的進步之一”。

我們生活在一個大數據的時代，但是絕大多數的數據都是“稀疏的”。想象一下，比如說，一個超大規模的表格，它存儲著所有的亞馬遜的顧客和所有商品的對應信息，如果一個顧客購買了某樣商品，就存儲一個“1”，否則為“0”。那么這個表格的絕大部分數據都會是 0。

面對這樣稀疏的數據，分析算法最終要做大量有 0 參與的加法和乘法，這是對計算資源的一種浪費。

程序員可以通過編寫特定的代碼來躲開零實體來規避這樣的問題，但是那樣的代碼是復雜的，而且只對非常有限的問題有效。

在 ACM 的 SPLASH（Systems, Programming, Languages and Applications: Software for Humanity）會議上，來自 MIT、法國的替代能源和原子能委員會和 Adobe Research 的研究者最近推出了一個新的系統，它可以自動產生針對稀疏數據的優化的代碼。

這樣的代碼比現存的未優化的軟件包快 100 倍。而且其性能可以與那些為特定稀疏數據操作而手動精心優化過的代碼相媲美，卻只需要程序編寫者做極少的工作。

這個用于稀疏代數編譯器的系統叫做Taco。根據計算機科學界的說法，一個像上文提到的，亞馬遜表格那樣的數據結構稱作矩陣，而一個張量僅僅是一個更高維的類似的東西。如果前面提到的亞馬遜的表格也保存著客戶、對應的商品、客戶對商品的評級以及評論中使用到的詞語，那么它將會是一個四維的張量。

“稀疏表示已經存在了超過 60 年”，MIT 電氣工程與計算科學的教授，新論文的主要作者 Saman Amarasinghe 說道，“但是沒有人知道如何為它們自動生成代碼。人們想到一些非常具體的操作——稀疏矩陣與向量相乘，稀疏矩陣與向量相乘再加上一個向量，稀疏矩陣與稀疏矩陣相乘，稀疏矩陣與稀疏矩陣相乘再與稀疏矩陣相乘。我們所做的***的貢獻就是實現了，當矩陣是稀疏的時候，可以為任何張量代數表達式自動生成代碼的能力。”

自定義核

近年來，對張量的數學操作——張量代數——對大數據分析和機器學習都變得至關重要。其實，從愛因斯坦時代起，它就成為科學研究中至關重要的部分。

在此之前，為了解決張量代數問題，數學軟件已經將張量操作分解成它們的組成部分。比如說，如果一個計算需要將兩個張量相乘然后再與第三個相加，軟件將會在前兩個張量上執行標準張量乘法操作，存儲結果，然后執行標準張量相加操作。

然而，在大數據時代，這個方法太費時間了。Kjolstad 解釋道，為了在數量龐大的數據集上執行高效的操作，張量的每個序列都需要它自己的“核”，或者說是計算模板。

“如果你在一個核中操作，你就能把所有操作一次完成，并且你可以讓它執行的更快一點，而不需要先將結果保存到內存中然后再把它讀回來以便和其他的東西相加”。Kjolstad 說，“你可以在一個循環中完成它。”

計算機科學的研究者已經研制出針對機器學習和大數據分析中常見張量操作的核，比如說上文中 Amarasinghe 列舉的。但是這些可能需要的核的數量是***的：比如說，將三個張量相加的核和將四個張量相加的核是不一樣的。而將三個三維張量相加的核和將三個四維張量相加的核也是不一樣的。

許多張量操作包括將來自一個張量的一個實體和來自另一個張量的一個實體相乘的操作。如果這兩個實體都是 0，那么他們的結果也是 0。而操縱龐大而稀疏的矩陣的程序就會浪費大量的時間來對 0 進行加和乘操作。

為稀疏張量手動優化的代碼識別出零實體并精簡包含他們的操作——在加法中只關注非零的實體并完全省略零實體參與的乘法。這使得張量操作更快，但是需要程序編寫者做大量的工作。

比如說，將兩個矩陣相乘的代碼，如果矩陣是稠密的（沒有實體可以被省略）可能只有 12 行。但是如果矩陣是稀松的，相同的操作可能需要 100 行或者更多的代碼來去處理應該被省略的部分。

引入 Taco

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

Taco 也使用一個高效的索引方案去存儲稀疏張量的非零值。如果包含 0 值，一個亞馬遜公開發布的，存儲客戶 ID、對應購買物品和從評論中提取的描述詞語的張量，會占用 107 億字節的數據，或者大說，約是估計出的的所有的谷歌服務器存儲容量 10 倍。而使用 Taco 的壓縮方案，它只占用 13 千兆字節，用一個智能手機就足夠存儲。

“在過去的二十年中，許多研究小組一直在嘗試解決稀疏矩陣的編譯優化和代碼自動生成問題，但是收效甚微。”俄亥俄州立大學計算機科學和工程的教授 Saday Sadayappan 說道，“最近 Fred 和 Saman 取得的進展代表著在這一長期存在的問題上根本性的突破”，他并沒有參與這項工作。

“他們的編譯器通過自動生成高效的代碼，現在已經可以讓應用程序的開發者用非常簡單，方便的高級符號來指定復雜的稀疏矩陣和張量計算”。他繼續說道，“對一些稀疏計算，編譯器生成的代碼已經和手動精心改進的一樣好甚至更好。它有望成為真正的游戲規則改變者，它是近年來在編譯優化領域最令人激動的進步之一。”

轉載自：DeepTech深科技 網易號