mur mur 我放在最下面 抱歉讓人見笑ㄌ 哈哈哈
這幾天換了一個完全新的題目水 (嘿嘿嘿
笑爛 但總之是個例子 也是我自己手刻(我跟AI一起 簡稱 我自己手刻 哈哈哈哈)
老黃曆了 先說個數學 在講個例子 然後提優化 最後會有一些我的小廢話
ok here we 夠~
OK 等一下 先不要go
我打完之後發現 狗e04長 但是 基本上不是太難的東西 大概吧?
總之 先不要被長度下到
前面幾天，我們一直在看 GEMM、FWT、Tensor Core，以及怎麼把一段計算塞進 GPU。
今天換一個看起來完全不像矩陣乘法的問題：我們要在平面上畫一張 graph，重新安排每個 node 的位置，讓某一條 edge 不要被其他 edges 穿過太多次。
如果你沒有接觸過圖論，這句話裡可能每個名詞都需要先解釋。所以今天先不急著碰 CUDA，我們從「什麼是 graph」開始。
圖論裡的 graph，不是折線圖、長條圖或圓餅圖。
它是一種描述「哪些物件彼此有關係」的資料結構：
Graph = Nodes + Edges
node 是我們關心的物件，也常被叫做 vertex。
例如：
社群網路
node = 使用者
交通網路
node = 車站
電路圖
node = 元件或接點
這個 LCN 題目
node = 要放在畫布上的一個點
edge 則表示兩個 nodes 之間存在連接關係：
社群網路
edge = 兩個人互相認識
交通網路
edge = 兩個車站之間有路線
電路圖
edge = 兩個接點之間有導線
這個 LCN 題目
edge = 兩個 nodes 之間必須畫一條直線
假設有四個 nodes：
V = {0, 1, 2, 3}
並且有四條 edges：
E = {
(0, 1),
(0, 2),
(1, 3),
(2, 3)
}
我們可以先把連接關係畫成：
node 0 ●────────● node 1
| |
| |
node 2 ●────────● node 3
這張小圖告訴我們：
node 0 連到 node 1、node 2
node 1 連到 node 0、node 3
node 2 連到 node 0、node 3
node 3 連到 node 1、node 2
Graph 通常寫成：
G = (V, E)
V = 所有 nodes 的集合
E = 所有 edges 的集合
到這裡，我們只有定義「誰和誰相連」。那四個 nodes 一定要排成正方形嗎？不一定。
同一張 graph 可以有很多種畫法。
我們可以把 node 0 放左上、node 1 放右下；也可以把 node 0 移到中央。只要 edges 仍然連接原本指定的端點，graph topology 就沒有改變。
不能修改的東西
哪些 nodes 存在
哪些 node pairs 之間有 edge
可以修改的東西
每個 node 的 x 座標
每個 node 的 y 座標
每個 node 的位置可以寫成：
pos[v] = (x[v], y[v])
所有 nodes 的位置合在一起，就是一份 layout：
layout = {
pos[0],
pos[1],
pos[2],
...
}
一條 edge e = (u, v) 則會被畫成 pos[u] 與 pos[v] 之間的直線線段：
node u ●────────────────● node v
<---- edge e ---->
這個差別非常重要：
graph
決定誰和誰相連
layout
決定這些 nodes 被放在哪裡
drawing
依照 layout，把每條 edge 畫成直線
Graph 沒有改，layout 一改，edges 在畫布上的走向就會跟著改。有些 layouts 很乾淨，有些 layouts 會讓大量 edges 互相穿越。
LCN 要搜尋的正是 layout。
輸入會給我們：
一張固定的 graph G = (V, E)
一個 width * height 的整數畫布
我們要替每個 node 選擇一組整數座標：
node v -> pos[v] = (x[v], y[v])
再把每一條 edge 畫成直線：
edge (u, v) -> segment(pos[u], pos[v])
最後要同時做到兩件事：
第一件事
layout 必須合法
nodes 不能重疊、不能跑出畫布
node 不能落在別人的 edge 上
edges 不能疊成同一段線
第二件事
讓 crossing 最嚴重的那一條 edge
被穿過的次數越少越好
可以先把完整題目壓成一行：
在所有合法的直線 graph layouts 中，
找到「單一 edge 最大 crossing 數」最小的 layout。
這句話就是後面所有 Crossing、Layout 與 SA 實作共同要解的問題。
現在我們可以來看一個有點奇怪的例子。
假設兩個 layouts 都有 4 個 crossing pairs：
Layout A 的 per-edge crossing counts
[4, 1, 1, 1, 1]
總 crossing pairs = (4 + 1 + 1 + 1 + 1) / 2
= 4
另一張圖則是：
Layout B 的 per-edge crossing counts
[2, 2, 2, 2]
總 crossing pairs = (2 + 2 + 2 + 2) / 2
= 4
兩張圖的 crossings 總數完全一樣。
如果我們只做一般的 crossing minimization，它們可能會被判成平手。但 LCN 會選 Layout B，因為 Layout A 有一條 edge 被穿過 4 次，Layout B 最嚴重的 edge 只被穿過 2 次。
Layout A -> K = 4
Layout B -> K = 2
這就是 LCN 最核心的想法：
不要只問整張圖總共有多少 crossings。
要問的是：
哪一條 edge 最慘？它被穿過了幾次？
Day 21 先把這個問題定義完整。今天不急著寫 CUDA kernel，也不急著談 simulated annealing。因為如果連「什麼答案比較好」都沒有固定下來，後面做的每一個 GPU 優化都可能只是在加速另一個問題。
對一個已經畫好的 layout，我們先數每一條 edge 被多少其他 edges 穿過：
c[e] = edge e 的 crossing count
再找出其中最大的值：
K(layout) = max(c[e])
這個 K 是這份 layout 的 local crossing number。它觀察的是單一 edge 承受的最壞情況，所以叫做 Local Crossing Number。
真正的圖論問題，還要在所有合法 layouts 裡面找最小值：
LCN(G) = min(
K(layout)
for every legal layout of graph G
)
所以這裡其實有兩層問題：
評分問題
給定一份 layout，算出它的 K
搜尋問題
在大量合法 layouts 裡，找到 K 最小的那一份
前者需要 Crossing evaluator；後者需要 Layout 與 SA。這也會成為後面幾篇文章的三條主線。
輸入資料大致包含：
width
height
nodes
edges
一份縮小過的 JSON 可以長這樣：
{
"width": 10,
"height": 10,
"nodes": [
{"id": 0, "x": 1, "y": 1},
{"id": 1, "x": 9, "y": 9},
{"id": 2, "x": 1, "y": 9},
{"id": 3, "x": 9, "y": 1}
],
"edges": [
{"id": 0, "source": 0, "target": 1},
{"id": 1, "source": 2, "target": 3}
]
}
理論中的 V、E 和 pos[v]，到了程式裡就是 nodes、edges、x、y。後面的 CPU 與 GPU 實作，最後都會把這些欄位整理成連續 arrays 來計算。
先把剛才的四個 nodes 畫出來：
node 2 ● ● node 1
\ /
\ /
\ /
/ \
/ \
/ \
node 0 ● ● node 3
存在的 edges 是：
edge 0 = (0, 1)
edge 1 = (2, 3)
兩條線段在內部穿過彼此，因此這裡有一個 crossing pair：
c[0] = 1
c[1] = 1
K = 1
注意：一個 crossing 會同時記在兩條 edges 上。
一個 crossing pair
-> edge 0 的 count 加 1
-> edge 1 的 count 加 1
所以：
sum(c[e]) = 2 * crossing_pair_count
這也是之後檢查程式是否算錯時，很好用的一個 invariant。
但是「兩條線碰在一起」有很多不同情況。只有其中一種會成為合法 layout 裡的 crossing。
這是最標準的 crossing：
A ● ● C
\ /
\ /
\ /
/ \
/ \
/ \
D ● ● B
兩條 edges 不共用 node，交點也不在任何端點上。
edge AB 與 edge CD
-> proper interior crossing
-> crossing count 加 1
B ●
/
/
A ●---------● C
edges AB 與 AC 都從 node A 出發。它們在 A 接起來，是 graph topology 本來就要求的連接，不是兩條 edges 互相穿越。
edge AB 與 edge AC
-> shared endpoint
-> 不算 crossing
如果忘記先排除共用端點，高 degree node 周圍會被灌進大量假的 crossings。
A ●---------● C ---------● B
假設 edge 是 AB，而 node C 並不是它的端點。C 剛好落在線段 AB 的內部。
這不能被當成「沒有 proper crossing，所以是 0」。它是一份不合法的 layout：
node C lies on edge AB
-> V3 violation
-> reject layout
A ●--------------● B
C ●--------------● D
如果兩條共線線段共享一段正長度區間，它們不是在一個點穿越，而是重疊。
edge AB overlaps edge CD
-> V4 violation
-> reject layout
這裡有一個很重要的區別：
crossing predicate 回傳 false
不一定代表 layout 合法。它也可能代表這根本不是 crossing evaluator 應該接受的幾何情況。
這個專案把必要的幾何合法性分成四類：
V1：node 必須嚴格位於畫布內
1 <= x <= width - 1
1 <= y <= height - 1
V2：不同 nodes 不能使用同一組座標
pos[u] != pos[v] for u != v
V3：node 不能落在非 incident edge 的內部
V4：兩條不同 edges 不能重疊一段正長度區間
validator 另外會檢查 directed edge 是否向上：
V5：y[target] > y[source]
在目前專案的 admission contract 裡，V1～V4 是 error；V5 被記成 warning，不會讓 official_cpu_k(...) 直接拒絕 layout。這個差別要說清楚，否則很容易把「幾何合法」與「符合 upward drawing 偏好」混在一起。
完整的評分順序是：
candidate layout
|
v
檢查 V1～V4
|
+---- 有 error ----> reject
|
v
計算每條 edge 的 crossing count
|
v
K = max(c[e])
這也解釋了一個最簡單的作弊方法為什麼行不通：把所有 nodes 放在同一點，crossing evaluator 也許看不到 proper crossing，但 V1～V4 validator 會先把它擋掉。
crossing count = 0
和：
這是一份合法、而且 K = 0 的 layout
是兩件不同的事。
對兩條 edges：
edge e = (a, b)
edge f = (c, d)
我們先排除共用端點：
if a == c or a == d or b == c or b == d:
not a crossing
接著要知道 C、D 分別落在直線 AB 的哪一側。這可以用二維 orientation：
orient(A, B, C) =
(B.x - A.x) * (C.y - A.y)
- (B.y - A.y) * (C.x - A.x)
結果的正負號代表 C 位於 AB 的哪一側：
orient(A, B, C) > 0 -> 一側
orient(A, B, C) < 0 -> 另一側
orient(A, B, C) = 0 -> 三點共線
兩條線段在內部互相穿越，需要同時滿足：
C 與 D 位於 AB 的不同側
而且
A 與 B 位於 CD 的不同側
把它寫成接近程式碼的形式：
opposite(x, y) =
(x < 0 and y > 0)
or
(x > 0 and y < 0)
proper_crossing(e, f) =
opposite(
orient(a, b, c),
orient(a, b, d)
)
and
opposite(
orient(c, d, a),
orient(c, d, b)
)
只比較正負號，不需要計算 slope，也沒有垂直線除以零的問題。
至於共線、重疊、node-on-edge 等退化情況，則交給前面的 geometry validator 判斷。這樣 crossing evaluator 與合法性檢查各自有清楚的責任。
LCN 的主要目標非常明確：
minimize K
但是搜尋時，很多 layouts 會有相同的 K。假設目前已經找到 K = 3，下一個 candidate 也是 K = 3，我們仍然需要知道它是不是往比較好的方向移動。
因此 solver 保存：
K = 最大的 per-edge crossing count
n_K = 有多少條 edge 的 crossing count 等於 K
Phi = 所有 per-edge crossing count 的平方和
C = crossing pairs 總數
計算方式是：
K = max(c[e])
n_K = count(c[e] == K)
Phi = sum(c[e] * c[e])
C = sum(c[e]) / 2
當 K = 0 時，專案把 n_K 也記成 0，避免把「所有零 crossing edges 的數量」當成仍需改善的 bottleneck 數量。
再按照下面的順序比較：
objective = (K, n_K, Phi, C)
數字越小越好
由左到右比較
前一欄相同，才比較下一欄
例如：
Layout X counts = [3, 3, 0]
K = 3
n_K = 2
Phi = 18
C = 3
另一份 layout：
Layout Y counts = [3, 1, 1, 1]
K = 3
n_K = 1
Phi = 12
C = 3
兩者的 K 和總 crossing pairs 都相同，但 Layout Y 只有一條 edge 卡在最壞值，所以 solver 會先選 Y。
這些 tie-breakers 是搜尋器用來辨認方向的工程目標；LCN 的主成績仍然是最前面的 K。不能為了讓 C 下降，接受一份 K 更差的 best solution。
到這裡，我們可以把 Day 21 的數學問題濃縮成：
given:
graph G = (V, E)
integer canvas width, height
choose:
integer position pos[v] = (x[v], y[v])
for every node v
subject to:
V1: every node is strictly inside the canvas
V2: no two nodes share a position
V3: no node lies inside another edge
V4: no two distinct edges overlap on a segment
compute:
c[e] = number of proper crossings on edge e
K = max(c[e])
minimize:
K
solver tie-break:
(K, n_K, Phi, C)
整個求解流程則是：
flowchart TD
A[讀入固定的 Graph] --> B[產生一份 node layout]
B --> C{V1 到 V4 合法嗎}
C -->|否| D[拒絕或修復]
C -->|是| E[計算所有 edge crossings]
E --> F[建立每條 edge 的 c e]
F --> G[得到 K、n K、Phi、C]
G --> H{比目前的解好嗎}
H -->|是| I[保存 best layout]
H -->|否| J[由 SA 決定接受或拒絕]
I --> K[提出下一個 layout]
J --> K
K --> C
後面要加速的，就是這張圖中的三大區域：
Crossing
快速算出 c[e]、K 與 tie-break objective
Layout
產生比較有希望、而且容易修成合法的初始位置
Simulated Annealing
在龐大的 layout 空間裡持續提出與篩選 moves
它們需要的 GPU 策略完全不同。Crossing 是大量 edge-pair predicates；Layout 同時包含規則的 all-pairs forces 與不規則的 adjacency；SA 則有狀態，而且下一步依賴這一步接受了什麼。
所以這個案例好玩的地方，是我們不能只把三段 for-loop 改成 CUDA，就宣布 GPU 加速完成。
今天我們只回答了一件事：LCN 到底要找什麼答案。
合法 layout
-> 數出每條 edge 的 crossing count
-> 找到最壞的 edge
-> 最小化 K
Day 22 會開始寫程式：先用 CPU 雙迴圈檢查所有 edge pairs，再把同一個工作直接搬到 GPU。
那一版會做很多重複工作，甚至故意把同一對 edges 算兩次。但它會提供一條非常重要的 correctness baseline，也會帶出第一個反直覺的 GPU 問題：
少算一次 crossing predicate
和
避免很多 threads 競爭同一個 counter
哪一個比較重要？
有了今天固定下來的數學與合法性 contract，我們下一篇才有資格談「怎樣算得更快」。
mur mur time-----
下面是我發稿當天 沒帶電腦 當場跟活動的兄弟 借了一台電腦
哈哈哈 超感謝
標題甚至是亂打
內容純是AI逐字稿
總之 我覺得很荒謬
哈哈哈哈
:
所以就是，呃，不好意思，我今天在外面，这边在外面，甚至是用语音录的稿。我很感谢那个，叫什么名字来着，叫什么名字来着，哈比，金豪，哈比。谢谢金豪，哈比，借我他的笔电，帮我这个ID帮我贴文。我的二十一天是他维持的，对啊，OK。干，我今天還开会，靠北。
先預告一下，我等下會再更新。我今天講的題目是那個叫做LCN least crossing number。那圖它去解決一個叫做 LCN 問題。LCN 問題是在講的是 least crossing number。你可以想是一個圖，一個圖本身它有很多的線跟 edge 連線在一起。這個 edge 連線在一起，本身它每個 edge 會有重疊。那 edge 的重疊當中，edge 跟 edge 之間你會要找某個 edge，它的節點是最……它跨過的線是最多的。那我們要讓這個跨過最多的線本身它最少化，要怎麼去做。這幾天，六天、九天、八天，隨便，大概會講這樣子的一個問題，然後用 GPU 加速去怎麼解決，然後我們會嘗試去從它的那個交換，到它的那個算法，到 SA，到怎麼去 parallelize SA 這件事情，大概會有這樣子的過程去講這樣的 GPU 加速。對。那我現在還在外面，再次謝謝金航，借我他的筆電。
iThome鐵人賽
看影片追技術