随着各个领域研究的问题日益复杂,对大规模科学计算需求的日益增加,并行处理技术与系统得到了飞速发展。从第一台大型机Cray-1到IBM仍在研发的BlueGene/P,以及我国刚研制成功的“天河一号”,计算机硬件的性能获得了极大提升。然而,软件的发展速度远落后于硬件,这些强大的硬件处理资源诞生的同时,也面临着资源的有效管理与利用问题。如何划分和分配处理的对象,提高系统的吞吐率和整体性能,成为大规模科学计算领域迫切需要解决的关键问题。图划分理论与方法,为解决该问题提供了有效途径。但是面对并行计算领域问题的日益复杂,现有的图划分模型和方法还存在很多不足。本文针对图划分模型在解决并行计算领域中出现的问题,进行了深入研究。主要工作包括以下几个方面:首先,研究并分析了从图划分产生以来图划分理论与方法的发展,并对图划分经典方法进行了分类与总结,包括:几何方法、组合方法、谱方法和多层划分方法等。其次,分析了传统划分模型存在的问题,包括通信开销度量标准问题,无向图模型的表达性问题。最后,本文借鉴了前人用数学规划方法解决原始图划分问题的工作,结合现在图划分在并行计算任务分配领域的应用,用有向图来表达数据依赖,将数学规划方法应用于并行计算任务分配的图划分问题中,建立了基于数学规划的图划分模型,用数学优化手段解决图划分问题,并且给出了有向图划分问题的数学规划求解方法。该类模型有以下优点:(1)解决了原有模型对非对称矩阵和矩形矩阵的支持问题。(2)能够表达多种通信开销的度量标准,更加符合并行计算的实际情况。(3)能够得到更好的划分结果,在保证负载均衡的同时,使通信开销更小。(4)该类模型比较灵活,容易修改,重用性强。通过实验证明,该类模型得到的划分边界要小于现有的主流方法,可以更好地应用于并行计算及其它领域。