经半个世纪的努力,计算机硬件设计已获得令人不可思议的提升并趋向于高性能低开销化。例如:IBM正在试图研发的蓝色基因P的目标是达到峰值1petaflops,处理节点达到256K个。在如此大规模分布式系统中,如果不能实现合理任务调度将使世界顶级计算机无用武之地。在国家自然科学基金赞助下,本文针对超大规模分布式系统负载平衡问题展开深入研究。主要工作包括以下几方面:首先,研究并分析了几种典型的完全集中式以及分布式策略在解决超大规模分布式系统负载平衡的局限性。集中式策略包括:贪婪策略(GreedyLB)、精细化策略(RefineLB)、正交递归半分策略(orthogonal recursive bisection algorithm,OrbLB)、贪婪通信策略(GreedyCommlLB)。分布式策略包括:相邻分配策略(Neighborhood Averaging)、任务偷取策略(Work-Stealing)。并通过仿真实验验证了集中式负载平衡策略在内存开销以及负载平衡开销存在的瓶颈以及分布式负载平衡策略CPU利用率低等缺点。其次,研究并分析了解决超大规模分布式系统负载平衡问题经典策略所存在的缺陷。包括层次策略以及混合式负载平衡策略的通讯开销以及负载平衡开销。然而,以上所有策略都是基于通讯是固定的或是不考虑通讯延迟开销,近几年的研究发现延迟依赖于通讯介质呈现出时变性。这是由于网络中的通信量、阻塞情况以及一些未知因素所决定。目前提出的基于延迟的负载平衡策略并不能针对该特性进行有效预测。最后,本文根据大规模分布式系统通讯开销时变的特点,提出一种基于随机延迟论的层次结构负载平衡策略。此策略具有以下三个特点:(1)应用通讯优化的层次结构减小超大规模机群的负载平衡开销。(2)考虑到节点计算速率以及通讯介质的随机延迟性。(3)通过广义神经网络理论建模进行延迟预测,从而优化任务通讯延迟及迁移延迟。此方法为基于延迟的一类负载平衡策略提供了优化方案。仿真实验验证了应用广义神经网络进行延迟预测优于目前同类预测算法,适用于超大规模机群。