图计算是大数据处理领域中一种重要的计算模式,用于解决社交网络分析、商品推荐、道路交通规划等领域中的重要问题。随着互联网、智能终端、社交媒体等技术的发展,图数据规模快速增长,从而给图的存储、访问和计算带来巨大的挑战。为应对这些挑战,系统领域研究者开发出许多图计算系统来管理、分析和挖掘大规模图数据。基于计算平台的不同,图计算系统通常分为三类:分布式图计算系统、共享内存图计算系统和外存模式图计算系统。其中,外存模式图计算系统因其较高的性价比和较好的可扩展性近些年来得到研究者的广泛关注。但因未能充分考虑图算法的访问特征以及内外存等系统资源的利用率,外存模式图计算系统通常面临处理性能差、用户使用体验差等问题。针对这些问题,本文开展了如下研究工作。为解决外存模式图计算系统面临的子图构建开销大的问题,本文提出了基于局部性优化的子图构建方法。这种方法在计算过程中同时维护顶点的入射边和出射边,并将这些边分别按照边的目的顶点和源顶点进行排序。通过这种数据组织方式,系统在子图构建过程中可以实现对顶点和边最大程度的顺序访问,从而充分利用数据访问的局部性提升缓存命中率,显著降低子图构建过程的开销。基于这种子图构建方法,构建了一个高效的外存模式图计算系统LOSC。为了提升系统整体性能,进一步采用了一种基于压缩的边存储方法和基于区间顶点的轻量化拷贝方法来分别提升存储和并行计算的效率。实验结果表明,基于局部性优化的子图构建方法相比现有的子图构建方法,子图构建开销平均降低10.3倍;LOSC相比于具有代表性的外存模式图计算系统Graph Chi和Grid Graph,系统整体性能平均提升6.9倍和3.5倍。为解决现有的外存模式图计算系统磁盘I/O效率低的问题,本文提出了基于应用特征的混合I/O访问和顶点更新策略。这种策略在计算过程中自适应的采用了两种计算模型:基于行导向的推送模型（Row-oriented Push,ROP）和基于列导向的拉取模型（Column-oriented Pull,COP）。ROP模型在计算时选择性的访问活跃顶点和活跃边,避免非活跃数据的加载。COP模型在计算时顺序访问所有的顶点和边,确保数据访问的局部性。系统根据不同图算法的数据访问特征在ROP和COP模型之间进行自适应的选择和切换,从而在I/O数据量和I/O访问局部性之间取得较好的平衡,极大的提升I/O效率。基于这种策略构建了一个高性能的外存模式图计算系统HUS-Graph。为了更好的支持这种策略,HUS-Graph还采用了双向子块的图表示形式和基于I/O开销的性能预测机制来分别提升数据访问的局部性和支持更准确的计算模型切换。实验结果表明,HUS-Graph相比于Graph Chi和Grid Graph,I/O访问数据量分别平均减少18.4倍和8.8倍,整体性能分别平均提升9.4倍和6.5倍。为解决现有的外存模式图计算系统在处理并发图计算（Concurrent Graph Processing,CGP）任务时面临的大量冗余访问和存储开销以及I/O冲突问题,本文提出了面向并发多任务的外存模式图计算模型。该计算模型在处理多个CGP任务时,将图数据划分为多个边块（edge block）存储在磁盘上,并按照统一和固定的顺序依次加载每个边块到内存中进行处理。当边块被加载到内存之后,多个CGP任务可以根据自身的计算特点并发的访问边块和进行顶点更新。通过这种方式,可以将多个CGP任务对图数据离散和随机的磁盘访问转换为统一且连续的访问,从而减少冗余的访问和存储开销以及避免CGP任务对磁盘带宽的竞争。基于这种计算模型构建了一个面向并发多任务的外存模式图计算系统Graph CP。为了进一步提升系统整体性能,Graph CP提出了一种工作窃取策略和基于收益评价的I/O访问模式来克服CGP任务间工作负载的不平衡以及提升I/O访问效率。相比于现有的面向CGP任务的图计算系统,Graph CP利用具有较高性价比和较好可扩展性的外存系统,能够避免现有工作采用分布式系统或共享内存系统所带来的较高的硬件成本和通信开销以及较差的可扩展性等问题。实验结果表明,Graph CP相比于外存模式图计算系统Grid Graph和Graph Z,以及面向并发多任务的图计算系统Seraph,I/O数据量分别平均减少5.3、4.1和2.7倍,系统整体性能平均提升10.3、4.6和2.1倍。