1.一种基于加权依赖图的并发程序执行轨迹静态简化方法，其特征在于，针对原始的并发程序执行轨迹，计算轨迹中所有事件的依赖关系，然后，根据事件的依赖关系构造初始的加权依赖图，进而在不打破事件依赖关系的前提下对初始的加权依赖图进行化简，最终选择已有的拓扑排序算法对简化后的加权依赖图进行拓扑排序，生成一个线性序列，即简化后的并发程序执行轨迹；该方法包括下列步骤：

1）事件依赖关系计算；

定义1：两事件的依赖关系总体分为本地依赖和远程依赖；

本地依赖：表示相邻两事件被同一个线程调用；

远程依赖：表示相邻两事件被两个不同线程调用；

定义2：两事件远程依赖可分为冲突依赖和同步依赖；

冲突依赖：表示相邻两事件被两个不同线程调用，且同时访问共享变量，且至少有一个是写访问，包括读写依赖、写读依赖和写写依赖；

同步依赖：具有同步原语的两事件构成的依赖关系，包括解锁加锁依赖、线程创建开启依赖、线程退出结束依赖和唤醒等待依赖；

从原始轨迹的第一个和第二个事件开始，依次判断两事件是否属于同一线程，将其分为本地依赖和远程依赖，进一步通过判断两个事件的类型，将其分为冲突依赖和同步依赖，并分别加入到相应的依赖关系列表中；

2）加权依赖图构建；

定义1：加权依赖图的边集包括本地边和远程边；

本地边：表示两端事件属于本地依赖关系；

远程边：表示两端事件属于远程依赖关系；

定义2：节点度表示节点的入度与出度之和；

定义3：边的权重表示该边两端节点的度之和；

使用步骤1）计算的事件依赖关系，按轨迹中事件的顺序，用本地边和远程边连接事件，构成一个初始的加权依赖图，构建依赖图过程中每添加一条本地边和远程边则更新节点度，进而更新本地边的权值；

3）加权依赖图简化；

定义1：可达性是指从起始节点出发，经过有限条边之后可以到达目的节点；

加权依赖图简化是一个迭代的过程，每次迭代从步骤2）构建好的初始加权依赖图中选择具有最小权值的本地边，判断其是否符合合并条件，如果从入节点到出节点除了本地边以外是不可达的，则说明在这两个节点之间没有其他依赖事件，可以合并，否则不能合并，合并后更新相关节点的度和相关边的权重，迭代进行直到所有的局部边被检查一遍，则加权依赖图化简过程结束；

4）拓扑排序；

定义1：拓扑排序是指将一个有向无环图中的所有节点排成一个线性序列，使得图中任意一对节点u和v，若边(u,v)存在于图中，则在线性序列中u仍出现在v之前；

定义2：上下文切换是指两个连续事件被不同的线程调用，这两个连续事件之间则发生了一次上下文切换；

对于步骤3）获得的简化后的加权依赖图，使用已有的拓扑排序算法生成一个线性序列，该序列则为最终的简化后并发程序执行轨迹，轨迹中事件的发生顺序仍遵守原始轨迹中的依赖关系，且轨迹中含有最少的上下文切换。

2.根据权利要求1所述的基于加权依赖图的并发程序执行轨迹静态简化方法，其特征在于，在步骤1）中，事件依赖关系通过原始轨迹中每相邻两个事件的所属线程和事件类型计算获得；事件依赖关系根据是否被同一个线程调用分为本地依赖和远程依赖；远程依赖可以进一步根据事件类型分为冲突依赖和同步依赖，冲突依赖的两个事件必须至少有一个为写访问，包括读写依赖、写读依赖和写写依赖，同步依赖包括解锁加锁依赖、线程创建开启依赖、线程退出结束依赖和唤醒等待依赖。

3.根据权利要求1所述的基于加权依赖图的并发程序执行轨迹静态简化方法，其特征在于，在步骤2）中，对原始轨迹中的所有事件根据步骤1）中计算的依赖关系构建初始的加权依赖图；只有当出现远程依赖时才新创建一个本地事件节点，否则加入到原来的本地事件节点中；每添加一条本地边和远程边要更新节点度，进而更新本地边的权值。

4.根据权利要求1所述的基于加权依赖图的并发程序执行轨迹静态简化方法，其特征在于，在步骤3）中，对初始的加权依赖图进行化简，生成简化后的加权依赖图；具体步骤如下：迭代地选择具有最小权值的本地边，判断该本地边两端的节点能否合并，即除了该本地边以外是否可达，只有在不可达的情况下，才可以进行合并，然后更新相关节点的度和相关边的权值，直到所有本地边都被检查一遍，即依赖图中没有可以合并的本地边。

5.根据权利要求1所述的基于加权依赖图的并发程序执行轨迹静态简化方法，其特征在于，在步骤4）中，对于一个简化后的加权依赖图，生成一个满足所有事件依赖关系的线性序列；具体步骤如下：针对简化后的加权依赖图，选择一个拓扑排序算法，然后根据选定的拓扑排序算法生成相应的线性序列，该序列即为简化后的并发程序执行轨迹，它满足原始轨迹中所有事件的依赖关系，且具有最少的上下文切换。