姓名：吳慶愷 ?學號：16020610024
轉載自：http://www.cesdn.com/emb-linux/industry-news/201711/05-7736.html ?有刪節(jié)
【嵌牛導讀】：張量計算從愛因斯坦時代起就是科學研究的重要內容叛拷。大數(shù)據(jù)時代饶号，大數(shù)據(jù)和機器學習對稀疏張量（絕大多數(shù)元素為 0 的稀疏數(shù)組）的計算要求越來越高牲蜀。
【嵌牛鼻子】：機器學習泥兰，一種浪費凉驻，特定稀疏數(shù)據(jù)融虽，至關重要铜犬，壓縮方案
【嵌牛提問】：對一些稀疏計算柑肴，編譯器生成的代碼已經(jīng)和手動精心改進的一樣好甚至更好霞揉。它有望成為真正的游戲規(guī)則改變者嗎？
【嵌牛正文】：張量計算從愛因斯坦時代起就是科學研究的重要內容晰骑。大數(shù)據(jù)時代适秩，大數(shù)據(jù)和機器學習對稀疏張量（絕大多數(shù)元素為 0 的稀疏數(shù)組）的計算要求越來越高。
近日硕舆，MIT 的一款新系統(tǒng)可以自動生成針對稀疏張量計算等操作的代碼秽荞，比當前常用的軟件包快 100 倍，被譽為“近年來在編譯優(yōu)化領域最令人激動的進步之一”抚官。
我們生活在一個大數(shù)據(jù)的時代扬跋，但是絕大多數(shù)的數(shù)據(jù)都是“稀疏的”。想象一下凌节，比如說钦听，一個超大規(guī)模的表格，它存儲著所有的亞馬遜的顧客和所有商品的對應信息倍奢，如果一個顧客購買了某樣商品彪见，就存儲一個“1”，否則為“0”娱挨。那么這個表格的絕大部分數(shù)據(jù)都會是 0。
面對這樣稀疏的數(shù)據(jù)捕犬，分析算法最終要做大量有 0 參與的加法和乘法跷坝，這是對計算資源的一種浪費酵镜。
程序員可以通過編寫特定的代碼來躲開零實體來規(guī)避這樣的問題，但是那樣的代碼是復雜的柴钻，而且只對非常有限的問題有效淮韭。
在 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ù)計算機科學界的說法畔乙，一個像上文提到的，亞馬遜表格那樣的數(shù)據(jù)結構稱作矩陣翩概，而一個張量僅僅是一個更高維的類似的東西牲距。如果前面提到的亞馬遜的表格也保存著客戶、對應的商品钥庇、客戶對商品的評級以及評論中使用到的詞語牍鞠，那么它將會是一個四維的張量。
“稀疏表示已經(jīng)存在了超過 60 年”评姨，MIT 電氣工程與計算科學的教授难述，新論文的主要作者 Saman Amarasinghe 說道，“但是沒有人知道如何為它們自動生成代碼参咙。人們想到一些非常具體的操作——稀疏矩陣與向量相乘龄广，稀疏矩陣與向量相乘再加上一個向量，稀疏矩陣與稀疏矩陣相乘蕴侧，稀疏矩陣與稀疏矩陣相乘再與稀疏矩陣相乘择同。我們所做的最大的貢獻就是實現(xiàn)了，當矩陣是稀疏的時候净宵，可以為任何張量代數(shù)表達式自動生成代碼的能力敲才。”
自定義核
近年來择葡，對張量的數(shù)學操作——張量代數(shù)——對大數(shù)據(jù)分析和機器學習都變得至關重要紧武。其實，從愛因斯坦時代起敏储，它就成為科學研究中至關重要的部分阻星。
在此之前，為了解決張量代數(shù)問題，數(shù)學軟件已經(jīng)將張量操作分解成它們的組成部分妥箕。比如說滥酥，如果一個計算需要將兩個張量相乘然后再與第三個相加，軟件將會在前兩個張量上執(zhí)行標準張量乘法操作畦幢，存儲結果坎吻，然后執(zhí)行標準張量相加操作。
然而宇葱，在大數(shù)據(jù)時代瘦真，這個方法太費時間了。Kjolstad 解釋道黍瞧，為了在數(shù)量龐大的數(shù)據(jù)集上執(zhí)行高效的操作诸尽，張量的每個序列都需要它自己的“核”，或者說是計算模板雷逆。
“如果你在一個核中操作弦讽，你就能把所有操作一次完成，并且你可以讓它執(zhí)行的更快一點膀哲，而不需要先將結果保存到內存中然后再把它讀回來以便和其他的東西相加”往产。Kjolstad 說，“你可以在一個循環(huán)中完成它某宪》麓澹”
計算機科學的研究者已經(jīng)研制出針對機器學習和大數(shù)據(jù)分析中常見張量操作的核，比如說上文中 Amarasinghe 列舉的兴喂。但是這些可能需要的核的數(shù)量是無限的：比如說蔼囊，將三個張量相加的核和將四個張量相加的核是不一樣的。而將三個三維張量相加的核和將三個四維張量相加的核也是不一樣的衣迷。
許多張量操作包括將來自一個張量的一個實體和來自另一個張量的一個實體相乘的操作畏鼓。如果這兩個實體都是 0，那么他們的結果也是 0壶谒。而操縱龐大而稀疏的矩陣的程序就會浪費大量的時間來對 0 進行加和乘操作云矫。
為稀疏張量手動優(yōu)化的代碼識別出零實體并精簡包含他們的操作——在加法中只關注非零的實體并完全省略零實體參與的乘法。這使得張量操作更快汗菜，但是需要程序編寫者做大量的工作让禀。
比如說，將兩個矩陣相乘的代碼陨界，如果矩陣是稠密的（沒有實體可以被省略）可能只有 12 行巡揍。但是如果矩陣是稀松的，相同的操作可能需要 100 行或者更多的代碼來去處理應該被省略的部分菌瘪。
引入 Taco
Taco 完全自動地添加額外的代碼腮敌。編程者只需要指定張量的大小，是稀疏的還是稠密的，以及存儲它的值的文件即可缀皱。對任何針對兩個張量的操作斗这，Taco 建立一個分層的映射地圖指出，首先啤斗，兩個張量哪一對相對的實體是非零的，其次赁咙，兩個張量中哪個實體和零配對钮莲。而所有 0 與 0 的配對將被直接遺棄。
Taco 也使用一個高效的索引方案去存儲稀疏張量的非零值彼水。如果包含 0 值崔拥，一個亞馬遜公開發(fā)布的，存儲客戶 ID凤覆、對應購買物品和從評論中提取的描述詞語的張量链瓦，會占用 107 億字節(jié)的數(shù)據(jù)，或者大說盯桦，約是估計出的的所有的谷歌服務器存儲容量 10 倍慈俯。而使用 Taco 的壓縮方案，它只占用 13 千兆字節(jié)拥峦，用一個智能手機就足夠存儲贴膘。
“在過去的二十年中，許多研究小組一直在嘗試解決稀疏矩陣的編譯優(yōu)化和代碼自動生成問題略号，但是收效甚微刑峡。”俄亥俄州立大學計算機科學和工程的教授 Saday Sadayappan 說道玄柠，“最近 Fred 和 Saman 取得的進展代表著在這一長期存在的問題上根本性的突破”突梦，他并沒有參與這項工作。
“他們的編譯器通過自動生成高效的代碼羽利，現(xiàn)在已經(jīng)可以讓應用程序的開發(fā)者用非常簡單宫患，方便的高級符號來指定復雜的稀疏矩陣和張量計算”。他繼續(xù)說道铐伴，“對一些稀疏計算撮奏，編譯器生成的代碼已經(jīng)和手動精心改進的一樣好甚至更好。它有望成為真正的游戲規(guī)則改變者当宴，它是近年來在編譯優(yōu)化領域最令人激動的進步之一畜吊。”
