结构力学求解器报告

结构力学求解器报告（精选5篇）

结构力学求解器报告 篇1

一、实习目的

结构力学上机实习使训练学生使用计算机进行结构计算的重要环节。通过实习，学生可以掌握如何使用计算机程序进行杆系结构的分析计算，进一步掌握结构力学课程的基本理论和基本概念。在此基础上，通过阅读有关程序设计框图，编写、调试结构力学程序，学生进一步提高运用计算机进行计算的能力，为后续课程的学习、毕业设计及今后工作中使用计算机进行计算打下良好的基础。

二、实习时间

大三上学期第19周星期一至星期五。

三、实习内容

本次实习以自学为主，学习如何使用结构力学求解器进行结构力学问题的求解，包括：二维平面结构（体系）的几何组成、静定、超静定、位移、内力、影响线、自由振动、弹性稳定、极限荷载等。对所有这些问题，求解器全部采用精确算法给出精确解答。

四、心得体会

第一天上机时，张老师对结构力学求解器的使用方法进行了简单的介绍，然后就是学生自己自学的时间了。每个学生都有自己对应的题目要完成，在完成这些题目的同时，我也逐渐对结构力学求解器的运用更加自如。

从刚开始的生疏到最后的熟练运用，我遇到了不少问题：①第一次使用在有些问题上拿不定注意，例如，在材料性质那一栏，我不知道是EA和EI的取值②第一次接触这个软件，在使用过程中不知道该如何下手，题目条件的输入顺序也很模糊。③经常会忘记添加荷载的单位，导致计算结果出现问题。④对于有些命令不能很明确的知道其用法，致使在使用时经常出错。在面对这些问题时，我一般都会向同学和老师寻求帮助，直到最终将问题解决。

通过这几天的上机实习，不仅让我进一步掌握了结构力学的知识，同时，还使我对结构力学求解器有了更深入的了解：

1.结构力学求解器首先是一个计算求解的强有效的工具。对于任意平面的结构，只要将参数输进求解器，就可以得到变形图和内力图，甚至还可以求得临界荷载等问题。

2.即便是结构力学的初学者，只要会用求解器，也可以用求解器来方便地求解许多结构的各类问题，以增强对结构受力特性的直观感受和切实体验。

3.书本中的方法并非所有类型的问题都可以解决，例如，不规则分布的荷载以及超静定结构用传统方法比较困难，但用求解器就较为简单。而且，用求解器求解问题时可以不忽略轴向变形等书本中忽略的条件，与实际更加相符。

结构力学求解器报告 篇2

结构力学求解器 (SM Solver———Structural Mechanics Solver, 以下简称为“求解器”) 是清华大学袁驷教授主持研发的结构力学分析计算软件, 能够求解经典结构力学课程中所涉及的杆系结构的几何组成、静定、超静定、位移、内力、影响线、包络图、自由振动、弹性稳定、极限荷载等问题。结构分析结果可以以三种方式显示:数值、图形和动画。这些显示方式能够让用户全方位地认识和理解分析结果, 尤其是图形和动画显示方式能够让用户直观地认识结构的各种性质。该软件算法先进、结果精确、界面友好、操作方便, 既可供教师拟题、改题、演练, 亦可供学生作题、解题、研习, 还可供工程技术人员设计、计算、验算之用。

求解器的界面主要由两个窗体组成:文档编辑器, 以下简称编辑器, 用来输入、编辑结构模型的命令数据文档 (扩展名为“INP”) ;具备常用的剪切、复制、粘贴等文本编辑功能, 如图1所示。图形观览器, 以下简称观览器, 用来即时显示各种相关图形, 如结构图、内力图等;具备常用的缩放、平移等图形显示功能, 如图2所示[1]。

2 结构力学求解器的建模方法

结构力学求解器的建模流程一般为:定义结点→定义单元→位移约束→材料性质→荷载条件等。软件提供了两种输入方式:

(1) 对话框输入:通过对话框输入命令, 命令输入后, 求解器自动检查命令格式, 若输入正确, 则立即显示在图形观览器中;若输入的命令格式有误, 则会给出相应的提示。采用对话框输入命令无需记忆命令格式, 还可以先对输入的命令进行“预览”, 以检查是否符合要求, 若输入有误, 则可对输入的命令进行修正后再“应用”。

(2) 命令行输入:直接在编辑器中输入命令行。求解器采用了类似于著名有限元分析软件ANSYS的命令语言, 每一条命令都以关键词作为先导, 关键词允许为英文字符或中文汉字, 便于学习和记忆。在命令中可以定义变量、按Fortran语法输入标准的数学表达式和标准的数学函数 (如:sqrt、exp、log、sin、cos、tan、atan等) , 便于修改数据和调整参数, 为参数化建模提供了技术基础。

3 结构力学求解器在应用中遇到的问题

在进行结构分析时, 对于同一类型的结构, 经常需要分析其在不同的结构尺寸、截面特性以及不同的荷载工况 (永久荷载、可变荷载、地震作用等) 下的力学性能。对于这样的问题, 如果采用结构力学求解器进行分析, 则每当任一结构参数发生变化时, 都需要重新建立结构分析模型, 或者在已有的模型上进行修改。然而, 无论是反复重新建模还是修改模型, 都是非常繁琐和枯燥的, 不但费时费力, 而且容易出错;因此, 需要改进结构力学求解器的建模方法以解决这个问题。

4 结构力学求解器的参数化建模方法

4.1 参数化建模方法简介

参数化建模方法不是采用具体数值, 而是采用参数 (变量) 建立模型, 通过简单的改变模型中的参数值, 就能建立新的模型[2]。参数化建模的参数不仅可以是几何参数, 还可以是材料性质、荷载参数等。对于同一类型的结构, 采用参数化建模方法, 不但能够避免反复重新建模或修改模型的重复劳动, 减少工作量, 提高建模效率;而且可以减少建模过程中的人为差错, 保证建模质量。

4.2 结构力学求解器参数化建模的流程及技术要点

本节以单跨等高排架结构为例, 说明结构力学求解器参数化建模的流程及技术要点。排架的计算简图如图3所示。

首先, 根据结构的形式、特点及分析要求确定模型参数, 在模型的命令数据文档 (扩展名为“INP”) 中, 利用变量定义模型参数, 并指定具体数值。模型参数一般包括几何参数、材料性质、荷载参数等, 所有参数必须采用统一的单位制。模型参数的数目应当合理, 若参数过少, 则不能满足结构分析的要求;反之, 若参数过多, 则会增加模型的复杂程度和建模难度。模型参数对应的变量名称应当具有良好的可读性, 其只能是字母和数字的组合, 并且首字符必须是字母。

如图3所示, 排架的几何参数包括:跨度、上柱高度、下柱高度、吊车梁高度, 详见表1。

根据排架结构的特点, 其材料性质仅需定义柱的相对抗弯刚度;因此, 钢筋混凝土的弹性模量设为1, 柱截面的惯性矩取相对值即可, 详见表2。

作用在排架结构上的荷载有恒载、屋面活荷载、雪荷载、积灰荷载、吊车荷载、风荷载以及地震作用等, 这些荷载在排架上的作用可以看作是柱顶力矩、牛腿顶面力矩、吊车梁顶水平力、柱顶水平力、全柱均布水平力这五种受力情况中的一种或者几种的组合;因此, 需要对这五种受力情况分别定义荷载参数, 每种受力情况的荷载参数包括:计算开关、方向参数、荷载数值, 以柱顶水平力作用时的情况为例, 其荷载参数详见表3。由于结构力学求解器的命令仅支持顺序结构, 不支持分支和循环结构;因此, 设置“计算开关”这一参数, 用于控制该受力情况是否参与计算。

模型参数定义完成以后, 即可按结构力学求解器的一般建模流程, 采用预先定义的参数建立模型。以柱顶水平力作用时的情况为例, 采用参数化建模方法建立的排架分析模型如图4所示, 图中的数字“1~8”为结点编码。此时, 定义荷载参数及加载的命令代码如下 (以字母“C”开头的命令行用于注释) , 其中除了柱顶水平力的“计算开关”设为“1”外, 其余受力情况的“计算开关”均应设为“0”。

在结构力学求解器中, 修改相应的几何参数、材料性质、荷载参数, 即可便捷的得到单跨等高排架结构在不同的结构尺寸、截面特性以及不同的荷载工况下的分析模型。

5 结语

本文介绍了结构力学求解器的参数化建模方法, 并以单跨等高排架结构为例, 说明了结构力学求解器参数化建模的流程及技术要点。采用参数化建模方法, 能够便捷地得到同一类型的结构在不同的结构尺寸、截面特性以及不同的荷载工况下的分析模型。在参数化建模的基础上, 可以编制前处理程序, 以实现常见结构的快捷建模。

参考文献

[1]袁驷, 叶康生, 袁征.《结构力学求解器》的算法与性能——第十届全国结构工程学术会议特邀报告[A].第十届全国结构工程学术会议论文集第Ⅰ卷[C].北京:《工程力学》期刊社, 2001.174-181.

射汽抽气器结构设计计算 篇3

基本符号：

m――质量流量，kg/s；

w――质量流量比；

γ――绝热指数；

η――效率；

M――马赫数； M――速度系数； P――压力，kPa； T――温度，K； A――截面面积，m； R――通用气体常数，kJ/kg・K 。 2*下标说明： c――抽气器出口； d――扩压管； e――被抽吸气体； n――工作喷嘴； p――工作喷嘴入口。1 前 言

射汽抽气器一般在实际应用中起到密封设备抽真空、冷凝器内不凝结气体的抽除及低压气体的压缩升压的作用，现已广泛应用于能源电力、空调制冷及石油化工等领域。射汽抽气器在工作中运行状态的好坏，除了与运行条件和操作水平有关以外，射汽抽气器本身的设计水平也是一个重要的影响因素。因此依据射汽抽气器实际运行条件，有针对性的设计射汽抽气器的结构，会得到工作性能相对优良的射汽抽气器。

用传统的计算方法设计射汽抽气器的结构时，多数是采用试算的方法，因此需进行多次烦琐的计算和手工查阅相关图表才能得出最后计算结果，且结果也只能是近似值。若将传统的计算方法和现代计算机相结合，开发出计算程序，省去人工计算时查阅图表和大量烦琐的计算，则会使射汽抽气器的结构设计计算得到了大大简化，同时可提高计算结果的精确性。

2 工作过程的具体描述与分析

射汽抽气器主要由工作喷嘴、混合室及扩压管三部分组成，其基本结构如图1所示。在结构上，工作喷嘴采用了缩放喷嘴的结构形式，这种结构可以在其出口获得超音速汽流。在混合室与扩压管之间还设有一段等截面的喉管，其作用是使工作蒸汽和被抽吸气体充分混合，以减少突然压缩损失和余速动能的损失。

- 1 -

www.paper.edu.cn

图1 射汽抽气器内工质的压力、速度变化曲线

为突出射汽抽气器工作过程中的主要特点，将抽气器内流动的工质当作理想气体处理，并假设工质在抽气器内的流动是一维稳态绝热流动。射汽抽气器内工质的压力、速度变化曲线如图1所示。

在上述假设的前提下，射汽抽气器的整个工作过程可分为三个阶段，具体描述如下： ⑴ p点截面→2点截面为工作蒸汽在工作喷嘴内的膨胀增速阶段。

较高压力的工作蒸汽在工作喷嘴入口处（p点）以低于声速的汽流速度进入射汽抽气器的工作喷嘴。在工作喷嘴的渐缩段流动时，其压力不断减少，速度不断增加。在工作喷嘴的喉部（最小截面处，1点），汽流速度达到音速，即马赫数等于1。工作蒸汽在进入工作喷嘴的渐扩段后，压力进一步下降，汽流速度进一步增加，达到超音速状态，在工作喷嘴出口截面处，工作蒸汽的汽流速度可达900－1200m/s。

⑵ 2点截面→3点截面为工作蒸汽与被抽吸气体的混合阶段。

工作蒸汽在工作喷嘴出口截面处所形成的高速汽流会在工作喷嘴出口附近形成真空区域，这样压力相对较高的被抽吸气体就会在压力差的作用下，被吸入到混合室内。被抽吸气体在e点被吸入抽气器，从e点流动到3点的过程中，速度不断增加，压力在e点→2点段不断下降到工作蒸汽在工作喷嘴出口截面处（2点）的压力。此后在混合室段和喉管前段（2→4）混合物的压力就一直保持恒定值，既有P2＝Ps＝P3＝P4。在混合室的前段（2→s），工作蒸汽与被抽吸气体开始混合。在高速工作蒸汽汽流的携带作用下，被抽吸气体的速度不断增加并达到超音速状态（在s点截面处达到音速）。而工作蒸汽因此速度不断下降，在混合室的后段（s→3）的某一截面处工作蒸汽与被抽吸气体的流动速度达到相同，之后保持恒定。在混合室的后段（s→3），工作蒸汽与被抽吸气体已经充分混合，混合物的压力在其进入喉管 - 2 -

www.paper.edu.cn

时已保持恒定。这里需要特别说明的是，s点截面的位置并不是固定的，它是随着抽气器运行条件的变化而变化的。

⑶ 3点截面→c点截面为工作蒸汽与被抽吸气体的混合物的压缩升压阶段。

混合物在喉管内流动的过程中，会在喉管内的某一截面（4点）产生激波的现象，激波会导致混合物压力的突升（从P4升高到P5）和汽流速度的突降（从超音速v4降到亚音速v5）。当混合物从喉管流入到扩压管内后，其部分动能转化为压能，从而使其流速进一步降低，压力进一步上升至需达到的压力值Pc。

3 计算数学模型的建立

3.1 基本假设

为研究问题方便,在建立射汽抽气器结构设计的简化计算数学模型前,做以下假设: ⑴ 将射汽抽气器内流动的工质当作理想气体处理；

⑵ 工质在射汽抽气器内的流动是一维稳态绝热流动，工作蒸汽在工作喷嘴内的流动是一个等熵膨胀过程，工作蒸汽与被抽吸气体的混合物在扩压管内的流动是一个等熵压缩过程；

⑶ 工作蒸汽与被抽吸气体在混合室内开始混合；

⑷ 工作蒸汽与被抽吸气体具有相同的比重和热比容；

⑸ 工作蒸汽和被抽吸气体都是处于饱和状态，且他们在进入射汽抽气器时的速度可忽略不计，混合物从扩压管排出时的速度可忽略不计。

3.2 建立计算数学模型

在上述假设前提下，射汽抽气器结构设计的简化计算数学模型为：

射汽抽气器内的质量平衡方程：

mp+me=mc （1）

被抽吸气体与工作蒸汽的质量流量比：

w=me/mp （2）

为了便于分析和计算，可用马赫数来描述工质的流动过程。工作蒸汽在工作喷嘴出口截面处所达到的马赫数：

Mp2 （3） 式中ηn为工作喷嘴效率，它与工作喷嘴的形状、表面粗糙度和前后压力等因素有关，一般其值可通过实验获得的线算图的查询获得，一般其取值范围为0.75～0.9之间。

被抽吸气体在工作喷嘴出口截面处所达到的马赫数：

Me2= （4） - 3 -

www.paper.edu.cn

由于抽气器内的混合过程定义为一维稳态、绝热的过程，所以此过程满足动量和能量守恒定律。通过动量和能量守恒方程的联立，即可获得

（5） M4*

其中上标为*的参数M *称为速度系数，它是流体速度与临界速度（或临界声速）之比。它与马赫数之间关系式为：

M=* （6） Me2*、Mp2*及M4都是通过（6）式计算得到的。

喉管内激波前后马赫数之间的关系式：

(γ?1)M2+1

M5=4 （7）

γM42?γ?12

激波前后压力比可通过动量守恒方程导出，其关系式为：

P41+γM52 （8） =2P51+γM4

通过上述对射汽抽气器内工作过程的具体描述和分析，可知P2＝P3＝P4。方程（8）就是在这个前提下得到的。同样下面所得到的其它方程也是以此为前提的。

扩压管内的.压力升高比为：

γ

Pc?ηd(γ?1)2?γ?1=?M5+1? （9） 2P5??

式中ηd为扩压管效率，同样它也是与扩压管的流道形状、表面形粗糙度和前后压力的

因素有关，一般其值可通过实验获得的线算图的查询获得，一般其取值范围为0.7～0.9之间。

工作喷嘴喉部（1点）截面面积为：

A1= （10） 1

2工作喷嘴喉部（1点）与喉管（3点）截面面积比为： ??P2?γ??P2????1????Pc???Pc??

?2????γ+1?1γ?11γ?1γA1Pc=iA3Pp????? （11） 12??T1+we?(1+w)??Tp?????γ?1???????γ1+?????

工作喷嘴出口（2点）与工作喷嘴喉部（1点）截面面积比为：

- 4 -

www.paper.edu.cn

（12）

4 结构计算程序设计

结构力学求解器报告 篇4

实验报告

班级：学号：姓名：上机时间：

一、实验目的与要求：

1、熟悉贪心算法的基本原理和适用范围；

2、使用贪心算法编程，求解最小生成树问题。

二、实验题目：

用贪心算法求解Prim算法

三、实验内容：

任选一种贪心算法（prim或Kruskal），求解最小生成树。对算法进行

描述和复杂性分析。编程实现。

四、问题描述：

设G=(V,E)是连通带权图，V={1,2,…,n}。构造G的最小生成树的Prim

算法的基本思想是：首先置S={1}，然后，只要S是V的真子集，就作如

下的贪心选择：选取满足条件i∈s，j∈V-S，且c[i][j]最小的边，将顶

点j添加到S中。这个过程一直进行到S=V时为止。在这个过程中选取到的所有边恰好构成G的一棵最小生成树。

五、问题分析与算法设计

六、实验结果及分析

七、实验总结

八、程序代码

#include

#include

#include

#include

#include

#define maxint 20

#define inf 700

int AllSelected(int n,int s[])

{

int i;

for(i = 1;i <= n;i++)

{

if(s[i] == 0)

return 0;

}

return 1;

}

void Prim(int n,int **c)

{

int lowcost[maxint];

int closest[maxint];

bools[maxint];s[1]=true;

for(int i=2;i<=n;i++)

{

lowcost[i]=c[1][i];

closest[i]=1;

s[i]=false;

}

for(i=1;i<=n;i++)

{

int min=inf;

int j=1;

for(int k=2;k<=n;k++)

{

if((lowcost[k]

{

min=lowcost[k];

j=k;

}

s[j]=true;

for(int k=2;k<=n;k++)

if((c[j][k]

{

lowcost[k]=c[j][k];closest[k]=j;

}

}

}

}

void main()

{

int n,i,j;

int **k;

printf(“请输入顶点个数:”);

scanf(“%d”,&n);

k=(int **)malloc(sizeof(int *)*(n + 1));

for(i = 1;i <= n;i++)

k[i] =(int *)malloc(sizeof(int)*(n+1));

printf(“输入顶点间的权值(自己到自己为0，没有路的为大于其他任何值的数):n”);for(i=1;i<=n;i++)

for(j=i;j<=n;j++)

{

printf(“k[%d][%d]=k[%d][%d]=”,i,j,j,i);

scanf(“%d”,&k[i][j]);

k[j][i]=k[i][j];

}

printf(“n”);

printf(“顶点t”);

for(i=1;i<=n;i++)

{

printf(“%dt”,i);

}

printf(“n”);

for(i=1;i<=n;i++)

{

printf(“%dt”,i);

for(j=1;j<=n;j++)

{

printf(“%dt”,k[i][j]);

}

printf(“n”);

}

printf(“n”);

Prim(n,k);

结构力学求解器报告 篇5

可满足性求解(satisfiability)是指,基于给定的一组布尔变量V={v1,v2,…,vn},及由这些变量构成的短句集合C={c1,c2,…,cm},求得满足该短句集合C的一组解V={v1,v2,…,vn}的算法,简称为SAT[1]。SAT目前被广泛用于多个应用领域,如软件验证、理论证明、微处理器验证、模块验证等,其最重要最成功的应用之一为数字系统的测试与验证[1]。

SAT求解的工业实例问题规模很大,求解变量数目已达到百万数量级,约束子句数目达到千万数量级,巨大的求解时间开销难以满足需求。因此,设计高效的求解算法对于实际应用具有重要的意义。SAT用于工业实例求解时,需要对大量的变量进行迭代传播,每次传播需处理的数据量很大,且不同数据传播过程之间无需信息交互,为并行化提供了前提。

GPU具有大量的处理单元,可对大规模数据进行并行处理。GPU计算性能的提高和编程模型的发展,使得GPU越来越多地应用于通用计算中,如线性代数[2]、分子动力学[3]、统计学[4]、工程科学[5]等。本文针对于SAT求解特点及GPU特性,提出一种CPU与GPU协同求解的思想,基于GPU设计并实现了SAT算法中的最耗时(占算法开销80%～90%)的BCP过程的并行化。最后通过随机生成k-SAT测试用例进行测试,取得了5.4～10.3加速比。

1 相关工作

1.1 SAT

SAT分为完全SAT和不完全SAT两类。完全SAT对于整个求解空间进行搜索,如有解,则给出;如无解,可证明问题不可满足。不完全SAT由于求解中带有随机性,不能用于证明。本文基于完全SAT进行研究。现有的完全SAT算法中主要应用包括一下几流程:分支选择(branching),BCP,冲突学习(Conflict-driven clause learning)与回退(Backtracking)[1]。其中冲突学习与回退的出现对于SAT的发展具有里程碑的意义,并出现了一些经典的求解器,如GRASP[6],CHAFF[7],SATO[8]等。现有主流完全SAT求解器主要基于DPLL(Davis-Putnam-Logemann-Loveland)算法框架(如图1所示)来实现的[9]。

make_branch_decision() 通过启发式策略从现有的自由变量中选取一个作为决策变量,对其进行赋值指派,该过程也叫做决策(decision)过程;

deduce() 函数对新指派的变量以单文字蕴含(unit implication)规则基于约束集进行传播;运用单文字规则传播的全过程称为布尔约束传播BCP。如果一个变量被不同的子句通过单文字规则同时指派成TURE和FALSE,则说明当前的指派存在冲突,算法进入冲突分析(conflict analysis)过程;

conflict_and_backtrack() 分析当前冲突产生的原因,并表示成子句形式插入到现有的约束集中,这个过程叫做冲突学习(conflict-driven learning);通过冲突学习会撤销一部分变量的指派,这个过程称为回退(backtracking)。

1.2 并行SAT

伴随着多核体系结构和多机系统的出现,相继出现了一些并行SAT算法。如PMinisat[10]中实现了多线程之间对短子句的共享;PSatZ[11]设计了Master/Slaver模型,从线程分别与主线程通信,由主线程动态调整已实现动态的负载均衡;PSATO[12]中也采用了Master/Slaver的结构,并提出了将从进程的信息进行备份的容错措施。PaSAT[13]中设计了共享空间来实现对于学习到的子句的共享。这些并行的SAT算法都是在原有算法的基础上,通过对搜索空间的划分,将问题划分成若干个子问题由多个线程分别执行求解,在每个线程内部仍然是原有的串行SAT算法。

近年来出现了很多硬件加速器,包括图形处理器(GPU),元件可编程逻辑阵列(FPGAs)以及Cell B.E.,利用这些硬件加速器的很多研究都取得了比较好的效果[14,15]。GPU最初只用于图形处理,伴随其性能提高和编程模型日益成熟,如NVIDIA的CUDA,AMD的Brook+等,如今已广泛应用于通用计算领域[2,3,4,5]。通过提取算法的可并行部分,设计计算核心,将任务以合理粒度划分成多个线程,经过线程处理器调度分配到各个流处理单元执行,即可实现程序的并行化处理。

John D.Davis等在文献[16]中提出通过FPGA实现对SAT的加速,并融入了冲突学习过程,取得了很好的实验效果。基于GPU的SAT并行研究很少,主要因为受GPU每个处理单元功能的局限,其对于复杂问题的应用还不成熟。Luo Zhongwen等在文献[17]提出将3-SAT问题编码并存储到GPU中来实现。该文的主要工作是将3-SAT算法在GPU上实现,验证了GPU对3-SAT的适用性,但是并没有充分利用GPU的特点进行算法加速的研究,因此算法的性能提高并不理想。

2 基于GPU的SAT算法BCP过程加速方法

为提高性能而出现的许多启发式策略使得部分算法结构粘性很大,因此完全将现有的“类chaff”的SAT移植到GPU上实现难度很大,且对性能提高会有很大的影响。BCP过程是SAT算法求解过程的核心部分(见图1 DPLL算法),占算法总开销高达80%～90%。且其本质是以单文字规则迭代传播,具有处理数据量庞大、运算简单的特点,适用于GPU处理。因此,我们以BCP过程作为基于GPU加速研究的主要目标,对于SAT求解算法中的变量选择和冲突分析与学习过程仍交由CPU来执行(如图2所示)。

现有的SAT求解器各模块设计相对独立,且模块之间提供了很好的交互接口,使得将GPU加速部分集成到不同的求解器中变得容易可行;将经由GPU加速的BCP部分集成到现有的SAT算法(如MiniSat等)中,即可实现更高效的SAT求解器。

2.1 GP_BCP设计

现有SAT算法的BCP过程设计的很精巧,每次迭代过程只需几千个时钟周期即可,使得通过GPU来获得可观的加速比很具有挑战性。因此,我们要充分利用GPU并行处理的特点充分利用程序的并行度,并使每次迭代过程尽量与问题规模无关。基于以上两点,我们提出了基于GPU并行加速的BCP过程:GP_BCP。

2.1.1 GP_BCP总体结构

(1) CPU&GPU通信

该模块通过PCIe总线从CPU接收选取的变量及其指派值,并将传播过程的推导结果及当前求解状态传送回CPU。为充分利用总线带宽、减少通信开销,我们基于数据预取思想,每次选择一组变量并对其进行指派,以数据块模式传送给GPU。

设置缓冲区存放该组指派,每次从中选取一个变量交由推理引擎进行处理直至缓冲区为空,再请求CPU重新选取一组变量传输。在推理过程中如产生冲突,只需作废缓冲区中指派而不需其他额外开销。通过以这种数据块为单位的集中传输模式,可充分利用传输带宽,减少通信次数与通信开销。

(2) 推理引擎

为变量与约束子句集合建立关联结构,每次给定决策变量及其指派后,推理引擎通过对关联的约束子句进行计算,从而推导出新的变量的指派值。

(3) 推导结果

经推理引擎处理后会导致两种结果状态:产生新的推导指派和遇到冲突。如产生新的推导指派,将其放入缓冲区以进行迭代传播,同时将其传送回CPU端更新变量指派值。这一步可通过异步传输实现,从而隐藏了传输开销。如产生冲突,需要终止推导过程并将冲突状态(包括冲突变量、冲突的原因)传送回CPU以进行冲突分析与学习。

2.1.2 基于GPU的新型推理引擎设计

推理引擎是GP_BCP的核心部分,决定算法的最终加速比。本部分主要介绍其实现的总体思想。

实际求解中,问题规模往往很大,甚至达到百万数量级变量数和千万数量级子句数。为提高传播效率,我们为变量与约束子句建立关联结构。每次选择新的变量进行指派时,只需对关联结构进行传播,使得传播开销与问题规模无关,极大减少了传播的开销。同时,对于关联结构中的每个约束子句,分布到GPU不同处理单元来并行处理。因此,每次迭代传播过程开销相当于串行算法中对一条约束子句进行传播的开销。

对每个关联子句运用推导规则:如果子句中只有一个文字未被指派且其他文字均被赋为FALSE,则剩下的文字就会被赋为TRUE,从而推出新的指派。基于Brook+编程模型为其设计计算核心,其伪代码如图4所示。

如图4代码,对每个与当前指派相关的子句进行推理,遍历子句中的每个文字。如果存在文字j,使得j之前和之后的文字均被指派为false,且j为undefined(未被指派),则可推导出新的指派j为true;如果子句中所有文字均已被指派为false,则产生冲突,返回冲突状态。

2.2 GP_BCP优化

在2.1节(2)的推理引擎设计中,通过将变量相关的子句分配到GPU多个处理单元上传播而实现并行,但并行度不够充分。为提高数据的并行度,将每次指派后产生的新的指派分组,以组为单位进行并行化传播。

每次选择变量进行指派并根据约束子句集进行传播过程中,由单文字蕴含规则可推导出新的指派值,称为推导指派。一般来说,问题规模越大,每次传播产生的推导指派的数目越多。经过对不同的求解实例进行测试,我们发现每次传播产生的推导指派数目最多可达到103的数量级。由于由同一个变量指派经传播派生出的推导指派,具有相同的decision level(决策级别,由同一指派经传播推导出的变量决策级别相同),对其同时传播不会更改程序的推导规则,对于冲突分析过程及回退不会产生影响。因此可将多个指派的传播过程并行执行,充分利用GPU并行处理单元,既可增大程序的并行度获取更好的加速比,又减少了GPU与CPU通信次数及通信开销。

对于不同的求解问题,与变量关联的子句规模不同,决定着如何将推导指派进行分组并行传播,决定着GP_BCP优化过程的设计。对于这个问题,可在求解前通过CPU进行预处理得到与变量关联的子句规模,将结果以参数形式传入GPU作为优化尺度,以设计实现GP_BCP的并行优化。如图5给出优化后的计算核心伪代码。

kernel表达了优化后的程序语义。在具体实现时,基于编程模型特点,可通过数据并行展开而使循环展开,从而分布到GPU每个处理单元执行inference(assignment i, attached clause j),从而实现多个指派并行传播。

3 性能评测

测试平台为4G内存、3G主频的HP服务器与AMD RadeonTM4890GPU。我们通过编写测试样本生成程序,随机生成k-SAT测试用例(3≪k≪6)[18]来对优化前后的GP_BCP进行测试,并选取高效的串行SAT求解算法MiniSat进行对比测试结果和分析。

对随机生成的k-SAT测试样本,来对初始的GP_BCP过程进行测试,相对于MiniSat的BCP过程,不同的测试样本取得了不同的加速比(见表1所示)。

由表1可见,对于不同的测试用例,GP_BCP所取得加速比并不相同。随着每个子句所含文字数的增加,加速效果呈增长趋势。这是由于随着测试用例中平均文字数目增加,每个文字相关的子句集增大,从而使每次选取变量指派并进行常量传播时程序的并行度增加,使得BCP过程的加速比更高。

以相同的测试用例对经过优化的GP_BCP进行测试,结果见表2所示。

由表2可知,经过优化GP_BCP过程更充分的利用了GPU并行处理能力,使GP_BCP数据处理并行度增大,相对于原有的GP_BCP,优化后的GP_BCP加速比明显增加。

图6所示给出GP_BCP过程优化前和优化后的性能提升情况的对比结果。

对比优化前后GP_BCP过程获得的加速比(图6),我们发现,经过优化后,3-SAT的GP_BCP性能提升幅度最大。而随着测试用例子句平均文字数的增加,性能提升幅度呈下降趋势。这是因为3-SAT平均文字数最小而使得优化前的GP_BCP数据并行度小,所以经优化后3-SAT的并行度大幅提高;而随着平均文字数增加,GP_BCP并行度增加,优化幅度减小。因此优化后的GP_BCP性能提高幅度呈下降趋势。

4 结 语

本文基于GPU实现了SAT算法的并行化加速研究,将SAT算法中BCP过程移植到GPU并行,实现了基于GPU的并行BCP过程GP_BCP,最后进行了测试。对于BCP过程并行化后,该部分取得了较好的加速效果,针对于不同的测试用例,取得了5.4～10.3的加速比。SAT算法本身及应用的特点决定了传播过程与冲突学习过程的频繁交互,而使得基于GPU的SAT算法整体性能提升有限。在以后的工作中,伴随着GPU单个处理单元处理能力的增强,期望能够将冲突学习及回退过程移植到GPU上处理,实现完全基于GPU的SAT算法,从而使效率有更大的提升。