随着并行计算机系统的发展,很多复杂问题(尤其是科学与工程应用)的求解已经成为可能。然而,一些不规则的非平衡应用总是需要异步的且连续的负载平衡,因而对于充分利用当前SMP集群系统的计算性能提出了巨大挑战。UTS正是为了刻画这些非平衡应用的性能而设计,它的实现主要是通过对一个树状结构的搜索空间执行深度优先搜索。OpenMP和MPI实现的标准UTS分别适用于共享存储和分布存储体系结构。然而,这两种标准非平衡树搜索实现有其显著弊端。首先,这两种UTS实现均不能充分利用当前SMP集群的计算能力。OpenMP实现的UTS因无法进行全局地址空间访问而不能扩展到整个集群上运行。MPI实现的UTS虽然可以在集群上直接运行,但是可扩展性极差。其次,这两种UTS实现都采用固定粒度的任务窃取策略来实现动态负载平衡,并不能充分实现负载平衡。UTS主要利用任务窃取策略来实现连续且异步的负载平衡。本文针对目前标准UTS实现的弊端,设计实现了一种基于MPI+OpenMP混合编程模型的动态粒度任务窃取策略。本文提出的动态粒度任务窃取策略能够显著加速非平衡树搜索,并且提高其在SMP集群上的可扩展性。本文的主要工作和贡献如下:第一,采用动态粒度策略对OpenMP实现的标准UTS进行优化,实现一种面向共享存储系统的动态粒度非平衡树搜索。在这种非平衡树搜索实现中,任务窃取粒度随着被释放的空闲线程的个数动态改变。从而使每个空闲线程的任务请求尽可能被满足,促进线程间负载平衡。与纯OpenMP实现的标准UTS相比,本文实现的面向共享存储系统的非平衡树搜索能够在获得较高性能的同时,极大拓宽窃取粒度参数的取值区间。第二,采用动态粒度策略对MPI实现的标准UTS进行优化,实现一种适合于分布式存储系统的、具有较低通信开销的动态粒度非平衡树搜索。接着采用MPI+OpenMP混合编程模型组合共享存储和分布式存储系统的动态粒度非平衡树搜索,从而实现一种适合于SMP集群的、具有强可扩展性的动态粒度非平衡树搜索。与纯MPI实现的标准UTS相比,本文提出的基于动态粒度策略的非平衡树搜索展现出很高的性能和极强的可扩展性。当SMP节点规模达到128时,我们实现的非平衡树搜索能够获得超过74%的并行效率。本文提出的非平衡树搜索实现能够获得的最大遍历速率是33.9亿结点/秒,这是纯MPI实现的标准UTS所获得的最高性能的2.28倍。