1. 研究目的与意义（文献综述）

目的：

本课题的目的是针对单机上的图处理过程，分析图处理任务的特点，总结图处理任务管理的挑战，基于图处理任务管理挑战，提出一种解决方案，提高管理效果以及资源利用率。

国内外研究现状：
目前，人们提出了多种图处理的方法，主要包括内存模式和外存模式，单机模式和分布式模式。
内存模式和外存模式：内存模式在进行图处理任务时需要将图数据全部加载到内存中，外存模式则是随着计算的需要，不断把外存中的图数据一点点加载到内存中，外存模式受到IO限制。但是，随着图规模的不断增大，内存模式将全部图数据加载到内存受到了挑战。
单机模式和分布式模式：单机模式采取纵向扩展方式，将廉价的外存作为内存的扩展，解决了内存资源有限问题，但是处理的速度受到磁盘和内存IO差异影响。使用分布式模式减少外存访问的延迟，但是成本会增加，而且图的复杂性对图的分区带来了难度。
图处理任务存在资源需求高、不规则、资源利用率低等挑战，需要加以控制。许多学者已经对任务管理理论做了相关研究。
李宁等引用经典控制理论，实现了整体控制，解决了共享资源的争用、高度可变的工作负载、不公平的吞吐量共享等因素导致不可预测的IO等待时间问题，满足了不同的负载有着不同的服务水平目标（SLO-Service Level Objective）要求。在具有可变计算工作负载的环境中控制任务，最坏案例分析技术（WCET）被广泛使用，保证动态变化且有限制执行时间的任务最后截止期限，但是，当平均执行时间小于最坏的情况执行时间（WCET）时，这些技术会导致大规模的设计。
L.Sha等提出基于生产状态的控制任务模型，反馈程序会周期性地触发，并根据有限的预测成本计算控制任务的最佳采样频率，但是反馈程序的稳定性和计算复杂性问题没有得到解决。
在弹性任务模型中，一个包含周期性任务的任务集可以看作一个线性弹簧序列，一个任务的利用率与弹簧的长度类似，为了处理过载问题，任务可能会改变它们的利用率。弹性任务模型应用于具有可变执行时间任务控制，将这种方法推广到控制系统中，如果它的控制任务被设计成以另一个速率运行，那么控制系统可能会发生退化。
University of Virginia的反馈控制实时调度项目中，反馈控制理论被用来设计控制调度算法，在不可预测的资源受限环境中为在线交易、敏捷开发和web服务器等应用提供服务质量保证。
这些控制算法存在共性，需要测量和反馈，控制器在提高准确度的同时，也带了额外的时间开销，反馈延迟等问题。
意义：
虽然经典的PID控制算法可以为动态、无规律的任务执行提供基础方法，但是在现实应用中却面临新的问题。因为被管理系统资源的敏感、实时性，所以管理方法必须考虑控制成本，平衡控制图处理任务成本与控制质量。
设计并实现可变采样周期调节算法，通过测试验证可行性，达到提高资源利用率、控制稳定性、提高图处理任务的执行效率的目的。

2. 研究的基本内容与方案

目标：
设计并实现可变采样周期调节算法，提高图处理任务的执行效率。

基本内容：
(1)研究具体图处理任务执行情况，总结图处理任务特点；
(2)根据图处理任务的特点，分析图处理任务管理的挑战；
(3)针对图处理任务管理挑战，设计并实现可变采样周期调节算法，对图处理任务进行管理；
(4)实现可变采样周期调节算法，设计测试方案，验证算法的可行性和优势。

技术方案：
(1)分析图处理任务特点。

3. 研究计划与安排

(1)2018/1/9—2018/1/15：查阅参考文献，明确选题；
(2)2018/1/16—2018/3/5：进一步阅读文献，并分析和总结；确定技术路线，完成并提交开题报告；
(3)2018/3/6—2018/4/30：系统架构、程序设计与开发、系统测试与完善；
(4)2018/5/1—2018/5/25：撰写论文初稿；修改论文，定稿并提交论文评审；
(5)2018/5/26—2018/6/6：准备论文答辩。

4. 参考文献（12篇以上）

[1]Siek J G, Lee L Q, Lumsdaine A. The Boost Graph Library: User Guide and Reference Manual, Portable Documents. Pearson Education, 2001.
[2]Alexandrov A, Bergmann R, Ewen S, et al. The stratosphere platform for big data analytics. The VLDB Journal, 2014, 23(6): 939-964.
[3]Malewicz G, Austern M H, Bik A J C, et al. Pregel: a system for large-scale graph processing. in: Proceedings of the 2010 ACM SIGMOD International Conference on Management of data. Indianapolis, IN, USA : ACM, 2010. 135-146.
[4]Bisseling R H, McColl W F. Scientific computing on bulk synchronous parallel architectures. 2001.
[5]Page L, Brin S, Motwani R, et al. The PageRank citation ranking: bringing order to the web. 1999.
[6]Avery C. Giraph: Large-scale graph processing infrastructure on hadoop. Proceedings of the Hadoop Summit. Santa Clara, 2011.
[7]Low Y, Bickson D, Gonzalez J, et al. Distributed GraphLab: a framework for machine learning and data mining in the cloud. Proceedings of the VLDB Endowment, 2012, 5(8): 716-727.
[8]Gonzalez J E, Low Y, Gu H, et al. Powergraph: Distributed graph-parallel computation on natural graphs. in: Proceedings of the 10th USENIX conference on Operating Systems Design and Implementation. Berkeley, CA, USA: USENIX Association , 2012. 17-30.
[9]Abou-Rjeili A, Karypis G. Multilevel algorithms for partitioning power-law graphs. in: Proceedings 20th IEEE International Parallel amp; Distributed Processing Symposium. Piscataway, NJ, USA: IEEE, 2006. 10 .
[10]Ding C H Q, He X, Zha H, et al. A min-max cut algorithm for graph partitioning and data clustering. in: Data Mining, 2001. ICDM 2001, Proceedings IEEE International Conference on. Piscataway, NJ, USA: IEEE, 2001. 107-114.
[11]Lumsdaine A, Gregor D, Hendrickson B, et al. Challenges in parallel graph processing. Parallel Processing Letters, 2007, 17(01): 5-20.
[12]Yoneki E, Roy A. Scale-up graph processing: a storage-centric view. in: First International Workshop on Graph Data Management Experiences and Systems. New York, NY, USA: ACM, 2013. 8.
[13]Malicevic J, Roy A, Zwaenepoel W. Scale-up graph processing in the cloud: challenges and solutions. in: Proceedings of the Fourth International Workshop on Cloud Data and Platforms. New York: ACM, 2014. 5-7
[14]Nilakant K, Dalibard V, Roy A, et al. PrefEdge: SSD prefetcher for large-scale graph traversal. in: Proceedings of International Conference on Systems and Storage. New York, NY, USA: ACM, 2014. 1-12.
[15]Kyrola A, Blelloch G E, Guestrin C. GraphChi: Large-Scale Graph Computation on Just a PC. in: Proceedings of the 10th conference on Symposium on Operating System Design and Implementation. New York, NY, USA: USENIX, 2012. 31-46
[16]Roy A, Mihailovic I, Zwaenepoel W. X-stream: Edge-centric graph processing using streaming partitions. in: Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles. New York, NY, USA: ACM, 2013. 472-488.
[17]Roy A, Bindschaedler L, Malicevic J, et al. Chaos: Scale-out graph processing from secondary storage. in: Proceedings of the 25th Symposium on Operating Systems Principles. New York, NY, USA : ACM, 2015. 410-424.
[18]鲍匡迪.多任务环境下的图处理系统研究[d].武汉：武汉光电国家实验室，2016.7
[19]曾金龙 肖新华 刘清.Docker开发实践[M].北京：人民邮电出版社，2015.7