没有合适的资源?快使用搜索试试~ 我知道了~
首页高性能计算:数值线性代数自动生成代码方法的研究
高性能计算是现代信息技术领域的重要分支,它通过并行处理和分布式系统来解决大规模、复杂的数学问题,特别是在数值线性代数方面。数值线性代数涉及矩阵运算、求解线性方程组、特征值问题等,对于科学计算、数据分析和机器学习等领域至关重要。本文档探讨了在高性能计算环境中,如何通过自动代码生成技术来优化数值线性代数算法的实现。 作者伊恩·马斯里亚在巴黎萨克雷大学完成的博士论文,聚焦于开发一种自动代码生成方法,旨在针对特定硬件架构,如GPU(图形处理器),设计高效的数值线性代数程序。这种方法结合了通用编程(Generative Programming)、数据结构表达式库(DSEL)以及生成式编程的概念,利用C++等语言工具,实现了算法的自动化设计和优化。 在论文中,作者强调了高效编程对于手机等嵌入式设备中复杂应用架构的重要性。为了提升这些架构的性能,自动代码生成技术能够根据硬件特性动态调整和优化算法,减少了手动编写适应不同硬件平台的重复工作。这不仅节省了开发时间,还提高了代码的可移植性和性能。 该论文的成果对于高性能计算社区有着实际价值,因为随着硬件的发展,如何最大化利用多核CPU和GPU的并行能力,成为了关键挑战。通过自动代码生成,研究人员可以更快地将理论算法转化为实际执行的高效代码,从而推动高性能计算在更多领域的应用,如天气预报、分子模拟、金融建模等。 这篇论文为高性能计算中的数值线性代数提供了新的工具和策略,促进了科研人员之间的知识共享,并对未来的硬件-软件协同优化产生了深远影响。同时,它也体现了开放获取档案馆(如HAL)在学术研究传播中的重要作用,使得这一创新成果能够广泛被学术界和工业界所利用。
资源详情
资源推荐
1.2.
求解稠密线性系统9
通过算法。根据所需的精度,可以选择几种算法来求解线性系统。
我们可以找到两种主要的方法来解决线性系统:直接法或迭代法。直接方法使
用有限的操作序列来提供精确解
x
,如果没有舍入误差。用于求解此类系统的常用
方法称为高斯消元法。它包括将一个方程的系数与其他方程的系数相加,以消除
一个变量,并继续这个过程,直到只剩下一个变量迭代方法从解
x
0
的近似值开始,
并连续计算一系列近似值
x
i
以改进解。在我们的工作中,我们专注于直接方法,通
常用于
解决稠密线性系统。直接方法提供了更高的数值精度和良好
的计算粒度,使其
更容易利用潜在的并行性。我们注意到存在的主要分解[57]:LU,Cholesky,
QR,SVD,LDL
T
。
LU:将一般矩阵A分解为L×U,其中L是单位下三角,U是上三角(约2×n
3
/3触
发器)。
Cholesky
:对称正定(
SPD
)矩阵
A
被分解为
A
=
LL
T
,其中
L是下三角形(约n
3
/3触发器)。
QR
:一个
m×n
矩阵
A
被分解为
A
=
QR
,其中
Q
是一
个
m×m
正交矩阵,
R
是一
个
m×n
上
三角矩阵(
2n
2
(
m-n/3
)触发器)
.
SVD
:将
m × n
矩阵
A
分解
为
A
=
U ×
VT
,
U
是
m × m
正交矩阵,
N
是
m × n
对角矩阵
(其中对角线包含A的奇异值),V是n × n正交矩阵V(计算N的代价约为
mn
2
次浮点运算).
LDL
T
:因式分解(使用对称旋转)是
PAP
T
=
LDL
T
,其中
P
是置换矩阵,
A
是对称不定
方阵,
L
是单位下三角形,
D
是块对角,块大小为
1×1
或
2×2
(约
n
3
/3
触发
器)。
1.2.1
LU
分解
LU分解[57,p.111]是一种没有主元的改进的高斯消去法对于一个方阵n,LU分解
的浮点运算次数约为2n
3
/3。对于稠密矩阵,LU分解通常在适当的位置执行。这意
味着输出因子
L
和
U
在因子分解期间覆盖矩阵
A
I
J
I
J
第1 数字图书馆适应并行化的问题
10个架构
算法1
LU
分解到位,无主元
输入:
A
是
n
×
n
矩阵
1
:
for
k
=
1:
n
−1do
2
:
for
i
=
k
+
1:
n
do
3:
A
(
i
,
k
)
=
A
(
i
,
k
)
/A
(
k
,
k
)
4
:结束
5:对于i
=
k
+
1:n,
6:对于
j=
k
+
1:n,
7:
A
(
i
,
j
)
=
A
(
i
,
j
)
−A
(
i
,
k
)
<$
A
(
k
,
j
)
8
:结束
9
:结束
10
:结束
LU分解通常使用旋转策略实现,因为没有旋转会出现几个重要问题例如,如
果在矩阵的对角线上发现零,则将发生除以零,导致数值错误。此外,如果对角
线上有小幅度的元素,则因子最终会增长太多,也会当在LU分解中使用部分旋转
时,我们注意
PA
=
LU
,其中
P
是置换矩阵。高斯消除的稳定性可以用生长因子来测
量[69]。增长因子衡量消除步骤后矩阵的条目与原始条目之间的比率在高斯消去法
下,方阵A的增长因子定义为:
g
n
(
A
)=
max
i
,
j
,
k
|
a
(
k
)
|max
i
,
j
|
a
i
,
j
|
其中
a
(
k
)
是在消除的步骤号
k
之后的索引(
i
,
j
)
的元素
[78].最常见的旋转策略称为部分旋转。它包括排列行而不是列,以确保pivot是其
列中最大的条目。对于高斯消去法的步骤j,部分主
元法产生如下结果:
|
a
j
,
j
|
>
>
|
a
i
,
j
|
对于
所有
i
>
j
。
这个
瓜拉
和
那个
||∞ ≤ 1
。
||
∞
≤
1.它的生长因子上限是
2
n
-1
,可以肯定
问题
[53]
。
、
1.2. 求解稠密线性系统11
算法2LU分解到位,部分主元
输入:
A
是一个
n×n
矩阵
1
:对于
k
=
1:
n
,
2:
index←k
3:对于i
=
k
+
1:n,
4: 如果|A(i
,
k)|>>|A(
指数,
k)|然后
5:index
=
i
6:如果结束
7
:结束
8: 交换行
k
和
索引
9:对于
i
=
k
+
1
:
n
,
10
:
A
(
i
,
k
)←
A
(
i
,
k
)
/A
(
k
,
k
)
11
:结束
12:对于i
=
k
+
1:n,
13:对于
j=
k
+
1
:
n
,
14: A(i
,
j)=
A(i
,
j)
−A(i
,
k)
<$
A(k
,
j)
15
:结束
16
:结束
17
:结束
旋转的缺点来自于通信成本,这是由于执行比较以找到枢轴以及导致的行交换
对于一个正方形矩阵,部分旋转需要
O
(
n
2
)次比较。 其他众所周知的旋转策略
是总旋转(O(n
3
)比较)和车旋转(O(1
)。
5n
3
/
4
log
n
)比较)。
LU分解是一种经典的技术,在高性能线性代数库中与不同的实现一起使用。
我们可以找到具有不同旋转策略、精度、迭代细化甚至混合精度的应用程序。出
于这个原因,我们使用
LU
分解及其各种形式作为稠密线性系统通用求解器的重要
组成部分,我们将在第2章详细介绍
1.2.2
QR分解
QR
分解
[57
,
p.246]
将矩阵
A
分解为上三角矩阵
R
和正交矩阵
Q
的乘积。这是用于解
决最小二乘问题的主要方法,该问题包括找到系统
Ax
=
b
的最小解。 这意味着解决
||Ax − b||
p
,
A
是
m × n
矩阵,对于定义的
p
。有多种方法来计算矩阵的
QR
分解在
这里,我们将集中在因式分解与Householder变换,可以在数值库中找到我们将在
第2章中描述如何实现基于这种QR分解的混合精度半正规方程
在QR分解过程中,对矩阵A应用Householder变换将删除对角线以下的每个条
目通过重复这个过程
n
-
两个
j
+1
M
第1 数字图书馆适应并行化的问题
12个架构
次,我们得到上三角矩阵
R
,使得:
H
n
H
n
−
1. H
1
A
=
R
。
我们注意到在因子分解期间计算的正交矩阵的形式为:
H
=
I
2
uu
T
.
||
u
||
如果我们设Q
=
H1
... H
n
,我们可以得到A = QR,这意味着我们有 Q
T
A
=
R.算
法
3
说明了
Golub
使用房子函数描述的
QR
分解
[57
,
p.237]
。
算法3HouseHolder QR到位,无旋转
输入:
A
是一
个
m×n
矩阵
1
:对于
k
=
1:
n
,
2:
[v
,
β]
=
house
(
A
(
j
:
m
,
j
))
3
:
v
j
=
[0
.
0
,
0
,
1
,
v
j
.... [v
j
]
T
4
:
β
j
=
2
2
1+ ||
A
(
j
+1:
m
,
j
||)的方式
5
:
A(j:m
,
j:n)=(I−
βvv
T
)A(j:m
,
j:n)
6
:
如果
j m
,则
7
:
A(j
+
1:m
,
j)=
v(2:
m-j+
1)
8:如果结束
9
:结束
我们注意到这种方法是已知的数值稳定
[139]
。
1.2.3
LAPACK
和
MAGMA
线性系统的求解器可以在LAPACK和MAGMA中找到,它们构成了编写稠密线性
代数通用库的构建块。这些库中给出的例程可以通过矩阵的静态属性来区分。这
些性质对应于稠密矩阵的结构,例如一般的、带的、对称的、正定的或三对角
的。可以考虑其他结构更常见的一类线性系统对应于一般的稠密矩阵。本研究的
重点是稠密矩阵,已经涵盖了广泛的应用。
我们下面描述的是实现的主要算法的指导方针然而,这并不代表实现,因为它
将取决于矩阵的结构以及目标体系结构。 LAPACK用于CPU,实现更简单,与算
法相匹配事实上,由于
MAGMA
是为
GPU
设计的,因此
CPU
和
GPU
之间的过渡必
须平滑,以确保最小的通信成本。
ǁ − ǁ
1.2.
求解稠密线性系统13
1.2.3.1
通用求解器
LAPACK/MAGMA中用于一般线性系统的求解器(xgesv,字母
x表示精度,实
数(
s
)、双实数(
d
)、复数(
c
)或双复数(
z
)
; ge
代表一般)基于具有部
分行旋转的LU分解。这种技术,称为高斯消除与部分
旋转在大多数数值库中实现,包括
LAPACK
和
MAGMA
,并用于
TOP500
列表的
LINPACK基准测试
为了求解线性方程组Ax
=
b,我们用P个置换矩阵,L个下三角形和U个上三角
形计算一个分解
PA
=
LU
然后通过连续求解三角系统
Ly
=
Pb
,然后是
Ux
=
y
来计算解
x
。
算法4用LU分解求解Ax
=
b
1:计算具有
P
置换矩阵、
L
下三角和
U
上三角的分解
PA
=
LU
2
:求解
Ly
=
Pb
。
3
:求解
Ux
=
y
。
4
:解为
x
。
在矩形矩阵的情况下,例程xgelsy使用矩阵的QR分解(可能具有列旋转)来求
解线性最小二乘问题
[20]
:
最小Ax
b
2
x∈
Rn
算法5用QR分解求解Ax
=
b
1:计算具有Q正交矩阵和R上三角矩阵的分解A
=
QR
2
:形式
d
=
Q
T
b
。
3
:通过向后替换求解
Rx
=
d
4:解为x。
这些因式分解的兴趣在于,我们可以将获得的因子重新用于其他计算,这些计
算也可能非常昂贵,例如计算条件数[69]或执行迭代精化[38]。在方阵的情况下,
我们将确定LAPACK中可用的三种类型的求解器,并将提到可以添加的其他类型
在矩形矩阵的情况下,我们可以确定一个唯一的求解器,这是例程
xgelsy
。
第一个是例程xgesv使用LU分解计算解决方案这可以被看作是当没有关于系统
的特定信息时的标准情况其他情况包括迭代细化和混合精度。
剩余113页未读,继续阅读
cpongm
- 粉丝: 5
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- C++标准程序库:权威指南
- Java解惑:奇数判断误区与改进方法
- C++编程必读:20种设计模式详解与实战
- LM3S8962微控制器数据手册
- 51单片机C语言实战教程:从入门到精通
- Spring3.0权威指南:JavaEE6实战
- Win32多线程程序设计详解
- Lucene2.9.1开发全攻略:从环境配置到索引创建
- 内存虚拟硬盘技术:提升电脑速度的秘密武器
- Java操作数据库:保存与显示图片到数据库及页面
- ISO14001:2004环境管理体系要求详解
- ShopExV4.8二次开发详解
- 企业形象与产品推广一站式网站建设技术方案揭秘
- Shopex二次开发:触发器与控制器重定向技术详解
- FPGA开发实战指南:创新设计与进阶技巧
- ShopExV4.8二次开发入门:解决升级问题与功能扩展
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功