[發明專利]基于GPU的稀疏矩陣LU分解方法

在審

• 申請號: 201310329479.9
• 申請日: 2013-07-31
• 公開（公告）號: CN103399841A
• 公開（公告）日: 2013-11-20
• 發明（設計）人: 任令;陳曉明;汪玉;楊華中
• 申請（專利權）人: 清華大學
• 主分類號: G06F17/16
• 分類號: G06F17/16
• 代理公司: 北京清亦華知識產權代理事務所(普通合伙) 11201
• 代理人: 張大威

技術領域

本發明涉及電子設計自動化與并行計算領域，特別涉及一種基于GPU的稀疏矩陣LU分解方法。

背景技術

稀疏矩陣LU分解是線性代數中的一項基本操作，在電路仿真、結構力學、經濟建模等許多領域有廣泛應用。在電路仿真中，電路被表示為矩陣，電路矩陣極其稀疏，通常每行只有約5個非零元，這是由在電路中（除少量電源、地、時鐘節點外）一個節點不能連接太多元件這一原因決定的。求解電路的過程，也就是利用稀疏矩陣LU分解求解稀疏矩陣方程Ax=b的過程。在一次電路仿真中，稀疏矩陣LU分解位于牛頓—拉夫森迭代和瞬態迭代兩層循環之中，需要迭代地進行很多次，這一步驟是當前最常用的電路仿真SPICE(Simulation?Program?with?Integrated?Circuit?Emphasis)的主要瓶頸。目前對超大規模集成電路的仿真的時間可能長達數周甚至數月。因此稀疏矩陣LU分解的并行化是一個急需解決的問題。

矩陣LU分解的目標是找到上三角矩陣L和下三角矩陣U使得

上述方程解為

lij=aij-Σk=1i-1lik·ukj,j≤i]]>

uij=(aij-Σk=1j-1lik·ukj)/ljj,j>i]]>

上式可以寫成

xi=ai-Σk=1i-1lik·uk]]>

l_ij=x_ij,j≤i