随着量子计算、光子计算、生物计算等新型计算,以及多种混合计算模式的出现,直接的并行程序设计工作将变得极为复杂且代价高昂,这自然地推动了自动并行化技术的发展。多年来,自动并行化受制于程序结构的复杂、语义信息的模糊,平台结构的不断演进,运行时的状态随机等诸多因素牵制而发展缓慢。因而,也需要新的模型和方法以产生新的突破点。本文则重点关注循环迭代空间的切片并行这一子领域。其基本思想是以数据依赖约束为基础,对程序的循环迭代空间进行划分,生成可在不同处理器上并行执行的语句实例子集,称其为切片。而实现切片间无同步(依赖)或弱同步(依赖)并行是切片并行所追求的目标。已有的方法通常以图论为基础。以子图的连通性来表达无同步切片。其数据依赖作用下的传递闭包(连通子图),通常以矩阵乘法为基础求得,这显然有不菲的计算量。本文则以置换(变换)群理论为基础,将数据依赖关系视为群元对基本集的作用,将传递闭包视为群作用下的轨道。进而将传统的并行切片划分问题转化为迭代空间上的群轨道求解问题。而利用群的对称性,可获得极为简洁的类陪集的轨道表示形式。以此为基础,可快速地实现切片的划分及切片内的代码扫描。更进一步,利用群的结构理论,可为多类型数据依赖的混合作用建立分层模型。使得无论对无同步切片,还是多约束条件下的有同步切片的划分,均能有效实现。我们首先对数据依赖进行分类,为不同类型的数据依赖建立不同的群轨道表示模型。而多种不同类型数据依赖的混合作用,导致各子轨道的合并。然后,我们将轨道直接作为并行切片,并追加序属性以实现切片内的扫描,从而实现并行。分类处理是本研究的基本方法,几乎贯穿于各章。具体内容包括:(1)针对可交换的数据依赖关系,建立Abelian群轨道表示模型及其切片方法。具体又分为一般化的Abelian群模型及算法,以及专门针对多维标准型依赖的平移群模型及算法。(2)针对仿射型数据依赖,提出了迭代空间的分解与像轨道合并框架。在这一框架下,将仿射型依赖按满秩和非满秩,以及一维和多维两个角度分为几类。针对不同类型提出不同的具体方法。对一维仿射依赖,提出超平面的分解与合并模型,先将“写”所诱导的超平面作为基本切片,然后在其它依赖的作用下,实现基本切片间的合并。而针对满秩型依赖,则让线程主动探测轨道,让所有线程探测轨道,而只让首部线程执行切片内的扫描,这种互相协同工作的模式,我们称之为自组织方法。而最后,这几种方法(包括平移群模型方法)均被纳入至空间分解框架中,分别作为子空间中的处理方法。(3)针对循环内嵌的分支程序,建立迭代空间分解模型。具体又依据条件将分支分为:仿射型、周期型、单调型、概率型等几种。然后分别针对每种类型,研究其迭代空间的几何或拓扑结构,在此基础上结合对应的数据依赖来实现切片划分。对于上述每类方法,均进行了相关的实验比较,并获得了较好的效果。