我們試著讓 Seam Carving 在 GPU 上跑更快——然後我們證明了為什麼它不能
完整論文：seam_carving.pdf · 程式碼：YuXiangLo/NTUPDP2026 與吳雅蓁、羅宇翔合作，台大平行程式設計，Spring 2026。 本專案獲得台大平行與分散式程式設計期末競賽 Top 10（共 40 組）。 發表影片嵌入如下，我們的上台時間從 38:30 開始。 起點 Seam carving 是一種 content-aware 的圖像縮放演算法。它不是裁切或縮放，而是移除圖片中「最不重要」的像素路徑——seam——同時保留視覺上重要的區域。效果出乎意料地好。 演算法主要有兩個沉重的步驟：先計算 energy map（梯度大小，對整張圖掃一遍）；再執行動態規劃（DP）找出從上到下代價最小的連通路徑。移除那條 seam，重複。 在 CPU 上，這對大圖來說很慢。單核心處理一張 8K 圖（7680×4320，約 3300 萬像素）每條 seam 可能要幾百毫秒。我們有 V100。Energy 計算是完美的平行問題。問題看起來很明顯：能快多少？ 我們原本預期找到一個新的優化方式，拿到一個漂亮的數字。最後我們證明了為什麼漂亮的數字在結構上不可能達到——而這才是更有趣的結果。 DP 的問題 用 Nsight Compute 對 1428×968 的圖做 profiling，問題立刻清楚了：DP kernel 佔每條 seam 牆上時間的 ~93%。其他全是雜訊。 DP 的遞推關係是： 1 M[i][j] = e[i][j] + min(M[i-1][j-1], M[i-1][j], M[i-1][j+1]) 每一行依賴上一行。全部 H 行都是串行的。每行內部的 W 列可以平行——但在第 i-1 行完成之前無法開始第 i 行，沒有任何重新排序能消除這個依賴。這就是我們一直碰到的牆。 ...