《圖處理加速架構研究》第二章【閱讀筆記及思考】

第 2 章 圖處理應用加速架構的研究背景與現狀

（吐槽：對事不對人，文章定位很迷——要說是給小白看吧，各種省略，零基礎恐怕要吐血了；要說是給已經有基礎的人看吧，裡面會出現一些特别低端的細節） 吐槽歸吐槽，對我還是有很大幫助滴。

主要内容是：

1. 圖計算典型算法+程式設計模型
2. 圖神經網絡模型
3. （圖計算加速架構+圖神經網絡加速架構）研究現狀

文章目錄

• • 第 2 章 圖處理應用加速架構的研究背景與現狀
  • • 2.1 圖與其廣泛的應用
    • 2.2 圖的特征與存儲格式
    • • 2.2.1 圖的特征
      • 2.2.2 圖的存儲格式
    • 2.3 圖計算應用
    • • 2.3.1 典型算法
      • 2.3.2 程式設計模型
    • 2.4 圖神經網絡
    • • 2.4.1 圖神經網絡模型
      • 2.4.2 典型圖神經網絡模型
    • 2.5 圖計算應用與圖神經網絡的比較
    • 2.6 傳統神經網絡與圖神經網絡的比較
    • 2.7 圖處理應用加速架構的研究現狀
    • • 2.7.1 圖計算應用的加速架構
      • 2.7.2 圖神經網絡的加速架構

2.1 圖與其廣泛的應用

泛泛而談。

2.2 圖的特征與存儲格式

2.2.1 圖的特征

1. 無結構特性：形狀不規則，鄰居數量不确定
2. 極度稀疏：A是稀疏矩陣
3. 幂律度分布：存在極少量度很高的節點，大量節點的度都很低——“名人效應”
4. 強群體結構：群體或社群結構

2.2.2 圖的存儲格式

鄰接矩陣可以用來存儲圖，但是因為稀疏性，很多位置都是0，浪費空間。

解決方案：CSR或CSC的方法。

以CSR（壓縮稀疏行）為例，它很像是資料結構中的塊索引方法，專門用一個offset數組記錄節點鄰居在edge數組中的偏移量，以便查edge表得到鄰居節點的ID。節點屬性在圖計算中一般是标量，而在圖神經網絡中是嵌入表示向量。這樣，我們就用更小的空間将節點和鄰居關系存儲到了記憶體中，起到了資料壓縮的目的。

這一部分對我的啟發還挺大的，圖畫的也挺好。

2.3 圖計算應用

不知道我了解的對不對，圖計算就可以了解為使用某種算法對圖中的節點或邊進行周遊，不同的算法有不同的周遊順序。

2.3.1 典型算法

文章中把圖計算應用算法分為2類：

1. 全節點周遊算法
2. 激活節點周遊算法

我感覺激活結點的概念其實就是回溯法、分支限界法中的活節點+擴充節點，就是這一輪馬上要進行周遊并展開鄰居的節點。

在激活節點周遊算法中，每次隻有部分節點被激活；而在全節點周遊算法中，每次所有節點都是激活節點。

全節點周遊算法：

1. PageRank（PR）。很著名的算法，也是圖表示學習中随機遊走方法的基石。

激活節點周遊算法：

1. BFS
2. DFS
3. SSSP：單源最短路（Dijkstra、Bellman-Ford）
4. SSWP：單源最寬路。從一個節點出發到某個節點，找到這樣一條路徑——這條路徑中weight最小的邊在和其他路徑中weight最小的邊相比是最大的。

   

   https://en.wikipedia.org/wiki/Widest_path_problem
5. CC：尋找強連通分量（子圖）。

2.3.2 程式設計模型

圖計算應用算法的程式設計模型，感覺是為了能夠将圖算法應用于加速架構而設計出的一種通用架構，隻需要執行個體化其中的函數就可以實作不同的圖算法。程式設計模型主要分2類：

1. VCPM（以節點為中心）
2. ECPM（以邊為中心）

程式設計模型又可以分為2個階段：（感覺這裡文章中的圖是對的，但是表述上有點問題）和MP-GNN架構驚人的相似！

1. Scatter（擴散）：将自身的屬性等資訊擴散給鄰居節點
2. Apply（更新）：鄰居節點根據“消息”更新自身的屬性

大概流程：

1. 對于每個激活節點，通過offset數組找到偏移量，再通過偏移量找到鄰居節點ID，然後通過Process_Edge函數對邊進行處理得到邊進行中間結果，最後通過Reduce函數歸約得到節點的臨時屬性。
2. 周遊每個節點，使用Apply函數更新并激活節點。

吐槽一下，文章裡面并沒有寫出各種符号的含義，隻能自己猜測，差評！

Process_Edge、Reduce和Apply三個是自定義函數，不同的算法需要定義不同的函數。圖計算程式設計模型通過對節點屬性進行變換巧妙地控制了節點的周遊順序！！！比如說，對于BFS來說，如果v.Prop越小就會越早被通路（如果已經被周遊過了則不會再被激活了，這點有點類似visit[]數組的作用）。

VCPM和ECPM的差別：

1. 訪存行為：VCPM對offset和節點屬性均存在細粒度訪存，而ECPM隻存在對于節點屬性的細粒度訪存。
2. 計算效率：VCPM每次隻周遊激活節點，而ECPM每次都要周遊所有的邊，效率低。

2.4 圖神經網絡

這一部分很多地方不嚴謹！！！建議直接去看Hamilton的《GRL_Book》和清華大學的那幾篇GNN綜述。

2.4.1 圖神經網絡模型

内容就不說了，直接說幾個我認為不太嚴謹的地方吧，感覺作者也是為了寫文章沒辦法了。

1. Aggregation階段直接簡化為了逐元素比較操作，這樣真的好嗎？！空域卷積的聚合函數通常都是含有參數的，很多模型為了提高表達能力，會用到RNN核、注意力機制等，很少有模型會直接簡單的element-wise了。
2. Aggregate函數的公式之間簡化為了self-loop，但實際上并不是這樣的，這隻是簡化政策之一，不能夠以偏概全。
3. Combine階段其實就是Update階段，正因為2.中提到的self-loop才能将更新函數寫成一種比較簡單的形式。
4. 關于Pool和Readout的内容感覺也不太準确，不過不是我關注的重點。
5. 術語不規範，讀者兩行淚。

2.4.2 典型圖神經網絡模型

介紹了GCN、GraphSAGE（原文提出了3種聚合函數，然而本文再次斷章取義地簡化了。。）、GINConv（聚合函數引入了可學習的參數）、DiffPool等模型。

2.5 圖計算應用與圖神經網絡的比較

相同點：都是用了類似消息傳遞的架構——聚合+更新。

不同點：

1. 節點屬性：标量 V.S. 向量、張量。圖計算中節點屬性一般是标量，而GNN中節點屬性是向量或張量，并且次元還可以不斷變化。
2. 聚合、更新操作：正因為節點屬性的表示方式不同，相應的操作也不相同（GNN的計算訪存比很高）。

2.6 傳統神經網絡與圖神經網絡的比較

相同點：學習+推斷

不同點：

1. 輸入：GNN是不規則的非歐空間，并且具有排列不變性
2. 應用場景：GNN的樣本并不要求是i.i.d.
3. 數學理論模型：GNN可以通過聯系進行推理，可解釋性好一些

2.7 圖處理應用加速架構的研究現狀

主要講了圖計算應用加速架構+GNN加速架構的研究現狀，看的我是一臉懵逼，完全是全新的領域。

2.7.1 圖計算應用的加速架構

這一部分介紹了幾種主流的加速平台。可能是因為完全沒有接觸過，是以也隻是看到一些表象。

看完之後，我感覺很多都是在解決訪存的問題。之前學過程式的空間局部性原理，但是感覺在圖計算中這一點并不容易做到。因為你在取資料的時候并不知道鄰居關系（到底該緩存哪些節點的資訊），周遊的時候需要在有限的片上存儲空間中存放節點資訊，然後根據實際通路的順序不斷地替換/淘汰節點的資訊（有點類似于cache），當然，這種操作越頻繁，延遲也就越大，速度當然就上不去。是以，盲目地訪存可能會導緻cache命中率很低，成為圖計算的瓶頸。

1. 基于FPGA的平台。可配置性強、部署快，主要用來提供通用性的架構，但是性能不太行（硬體資源有限）。
2. 基于ASIC的平台。性能高，但是依賴大容量的片上存儲和分塊方法，伸縮性差。有個問題：分塊指的是什麼？類似于cache的組相聯隻能從某一分塊中進行淘汰嗎？
3. 基于NDP的平台。工藝還不成熟……
4. 基于NSP的平台。在SSD上加上額外的訪存處理單元，以減少在處理大規模圖的時候cache不命中所導緻的頻繁的資料替換，但是帶寬及其使用率比較低。
5. 基于PIM的平台。通用性較差。

2.7.2 圖神經網絡的加速架構

這一部分我直呼“好家夥”！

大概意思是說，本文提出了第一個圖神經網絡加速架構HyGCN，并在此基礎上提出了可重配置圖神經網絡加速架構UFlowGCN。文章中說，HyGCN解決了圖周遊中的不規則性對性能的影響，還能利用規則性提高神經網絡變換的執行效率，并能融合圖周遊和神經網絡變換的執行。

這部分内容在第四章會進行詳細的闡述。