现在,并行计算的平台绝大部分是分布式并行系统。分布式并行系统能否快速有效处理并行计算,除了依赖于分布式并行系统性能、网络带宽、并行算法等,还与任务分配和调度顺序有关。以一种合适的顺序将任务分配到处理器群上,以便提高系统使用效率和减少周转时间是任务分配的目。图划分算法为任务分配问题提供了解决方法。将任务分配问题转换为图模型,使用图划分算法解决任务分配问题。本文的研究环境是异构的分布式并行系统,使用任务交互图(TIG)和多层图划分算法来研究任务分配问题。多层图划分算法分为三个阶段：粗化(聚类)阶段、初始化分阶段和细化阶段。以往的聚类方法中,某两个任务是否能聚类仅仅取决于它们之间的通信代价。然而这是不够准确的,如果一个任务能被分配到一个更好的处理器上,也即在这个处理器上该任务总的执行代价要优于在之前的处理器上的执行代价。因此本文提出的聚类启发式算法考虑了任务之间的通信代价以及它们的不同。同时,任务分配到处理器的顺序会影响分配质量,因此本文提出了在两阶段方法中采用改进的度量方式来决定分配顺序,并在细化阶段改进了FM算法。最后,本文提出了一种基于迭代改进的启发式多层划分算法NTAT。文中提出的改进的任务分配算法是静态的,也就是说在程序开始执行时任务分配已经完成。但是,很多应用中可能会使用动态的任务分配方法以适应各种突然出现的情况,如工作量增加、处理器故障和链路故障等。改进的算法不适于动态划分的情况,因为动态的任务分配方法需要考虑与系统组件之间的交互,如与进程迁移机制的交互,同时还必须考虑其在细化阶段时的代价。因此,本文所有算法的改进是在静态划分的基础上进行的。