基于多核分布式环境下的任务调度关键技术研究
|
摘要
本文在系统分析了多核处理器体系结构的基础上，综述了任务调度的研究现状及多核处理器任务调度所面临的难题。
从多核处理器的静态任务调度入手，综合使用了任务分簇技术和任务复制技术，本文提出了一种面向同构多核处理器的任务调度算法，该算法通过减小任务间的通信代价，最小化了任务调度长度，并实现了核间的负载平衡。仿真实验证明本文算法具有优于遗传算法的性能。
针对多核集群的两级存储机制和三层通信结构，本文提出了一种面向多核集群的静态任务调度算法，该算法包括两轮操作：进程到处理器节点的分配；线程到处理核心节点的分配。每轮操作又分别包含了分簇策略和调整策略。通过三组对比实验表明本文算法具有较短的任务完成时间，且随着CCR的增大，本文算法的性能优势愈加显著。
通过对影响多核处理器动态负载平衡的各个因素的详细分析，本文设计了基于多核处理器的动态负载平衡模型，用五元组<负载平衡环境，任务属性，负载评价，调度策略，调度评价指标>形式化地描述了影响多核动态负载平衡的各个因素。
本文提出了一种树型计算环境下面向异构多核集群的独立任务调度算法。该算法首先建立了基于主-从树型模型的计算平台，然后通过预处理机制获取了每个处理核心的最优任务分配方案、每个处理核心的实时计算能力、核间通信能力和限制系数等实时状态信息。依据预处理机制，提出了基于最优任务分配方案的两种启发式算法：限制系数优先启发式算法和带宽优先启发式算法。实验数据表明本文提出的两种算法均优于Min-Min算法。
Along with the development of multi-core technology, the number of processing cores inthe processor has been increasing rapidly. In order to take full advantage of the huge amountof parallel computing resources, a highly efficient task scheduling mechanism is needed. Thispaper focuses on the research on key techniques of task scheduling based on multi-coredistributed environment, which has helped get to the shortest total execution time of theparallel tasks through reasonable scheduling tasks to each processing core.
Firstly, this paper elaborated on the structural characteristics of multi-core processorsfrom the development of multi-core processor structure and classification, and further studiedthe research status and problems of task scheduling that we’ve been facing under thedistributed environment. And then for static task scheduling, this paper proposed one taskscheduling algorithm for multi-core processors, and the other algorithm for multi-coreclusters; for dynamic task scheduling, this paper designed a dynamic load balancing modelbased on multi-core processors, and proposed a independent tasks scheduling algorithm ontree-based computing environments for heterogeneous multi-core clusters.
The main research work of this paper can be summarized as follows:
(1) This paper studied the problems of multi-task static scheduling based on theenvironment of a multi-core processor.
With the rapid growth of the quantity of processing cores in one processor, how toefficiently use these processing cores to get a minimum task execution time becomes the goalof task scheduling based on multi-core processors. In order to achieve this goal, the author hasbeen studying in two different aspects: How to reduce the communication cost among taskswhich were allocated to different processing cores; how to allocate tasks to improve theutilization of processing cores. This paper built a scheduling model based on the DAG, andthen proposed a task scheduling algorithm which combined task clustering with taskduplication technology. The algorithm includes three steps: firstly, changing task Graph fromDAG to in-tree graph; secondly according to in-tree graph, generating scheduling group or set;lastly adjusting scheduling set according to the number of processing cores. With taskreplication and clustering technology, the algorithm has reduced communication overheadamong tasks. Meanwhile the task completion time is kept a relatively lower value by using theload threshold, the load among cores is balanced and the utilization of processing cores isimproved. The time complexity of the algorithm is no more than several classical algorithms. Compared to genetic algorithm simulation experiment data shows that the proposed algorithmcan obtain near-optimal solutions in a relatively shorter time, and with the increasement ofcommunication overhead among tasks, the proposed algorithm shows a better performance.
(2) This paper studied the task scheduling problem for multi-core clusters.
With the architecture of high-performance general microprocessor into the multi-core era,multi-core processors have been increasingly used in cluster systems. Due to the introductionof multi-core processors, multi-core clusters include a two-level storage mechanism andthree-layer communication structure, which made the task scheduling problem for multi-coreclusters more complicated. In order to efficiently carry out the task allocation in a multi-corecluster, firstly, we built a task allocation model based on DAG, and then based on thetwo-level storage structure of multi-core clusters, this paper proposed a two-round taskscheduling algorithm, which scheduled tasks by level. According to the algorithm, theprocesses are assigned to processor nodes in the first round and the threads of processes areassigned to processing cores in the second round respectively. Towards three-layercommunication structure of multi-core clusters, in order to reduce the communicationoverhead, and achieve the earliest start time of current task, each round operation includestwo strategies: clustering strategy and adjust strategy. By reducing the inter-taskcommunication overhead， The algorithm minimizes the task scheduling length; Thealgorithm maintains load balancing between the two-level processing nodes by the loadthreshold, which improves the utilization of the processing core. Through comparison withrelated work, we can see that the time complexity of the algorithm is not more than similaralgorithms; three sets of comparative experiments show that the normalized schedule lengthof the proposed algorithm is less than the other two classic algorithms, and withCCR(communication to computation ratio) value being increased in DAG, the superiority ofthe proposed algorithm is prominent.
(3) This paper studied the five elements that affect the dynamic load balancing ofmulti-core processors.
Because dynamic load balancing algorithm can adapt to changes of nod loads, it is muchmore flexible and effective than static algorithm. However, dynamic algorithm will generatemore overhead than the static algorithm due to needs of collecting and analyzing stateinformation, but usually the cost is worthwhile. Based on the research on the problems of loadbalancing and scheduling for multiprocessors, according to the characteristics of CMP, wecarried out a detailed analysis of the various factors that affect the load balancing ofmulti-core processor. According to the above research, this paper proposes a formaldescription of a general model: utilizing a quintuple to express load balancing scheduling problem based on CMP. The modelcompletely expresses various elements of dynamic load balancing. The model provides comprehensive theoretical study guidance for research on dynamic load balancing onmulti-core processor.
(4) This paper studied the independent task dynamic scheduling problem forheterogeneous multi-core clusters.
The task scheduling mechanism based on homogeneous multi-core processor assignstasks to each processing core due to the number of tasks, but the task scheduling mechanismbased on heterogeneous multi-core assigned tasks to the processing cores which areappropriate for running the tasks according to the different properties of the task. The taskscheduling mechanism based on homogeneous multi-core processor assigns tasks to eachprocessing core due to the number of tasks, but the task scheduling mechanism based onheterogeneous multi-core assigned tasks to the processing cores which are appropriate forrunning the tasks according to the different properties of the task. Because processing core isheterogeneous, it increases the difficulty of the task scheduling. In this paper tree-basedmaster-slave model is applied to heterogeneous multi-core cluster, and each computing nodecorresponds to a processing core. This paper has researched and analyzed the classicindependent task scheduling problems and the master-slave tree-based computingenvironment, which built a pre-processing mechanism, through that we can gain the optimalnumber of tasks assigned to each core, real-time network communication ability among thecores and Real-time calculation ability of each processing core with load. Throughcomprehensive analyzing communication ability and calculation ability, we can obtainquantitative limit coefficient, which is used to evaluate the performance of the pros and consfor the target processing core. The paper proposed two heuristic algorithms based on theoptimal task scheduling scheme: a prior-limit-coefficient heuristic algorithm and aprior-bandwidth heuristic algorithm. Using the SimGrid platforms, this paper constructed andimplemented these two algorithms, and the experimental results show that the proposed twoalgorithms are better than Min-Min algorithm, and with the increasing number of tasks, theproposed algorithm shows more performance advantage than Min-Min algorithm.
从多核处理器的静态任务调度入手，综合使用了任务分簇技术和任务复制技术，本文提出了一种面向同构多核处理器的任务调度算法，该算法通过减小任务间的通信代价，最小化了任务调度长度，并实现了核间的负载平衡。仿真实验证明本文算法具有优于遗传算法的性能。
针对多核集群的两级存储机制和三层通信结构，本文提出了一种面向多核集群的静态任务调度算法，该算法包括两轮操作：进程到处理器节点的分配；线程到处理核心节点的分配。每轮操作又分别包含了分簇策略和调整策略。通过三组对比实验表明本文算法具有较短的任务完成时间，且随着CCR的增大，本文算法的性能优势愈加显著。
通过对影响多核处理器动态负载平衡的各个因素的详细分析，本文设计了基于多核处理器的动态负载平衡模型，用五元组<负载平衡环境，任务属性，负载评价，调度策略，调度评价指标>形式化地描述了影响多核动态负载平衡的各个因素。
本文提出了一种树型计算环境下面向异构多核集群的独立任务调度算法。该算法首先建立了基于主-从树型模型的计算平台，然后通过预处理机制获取了每个处理核心的最优任务分配方案、每个处理核心的实时计算能力、核间通信能力和限制系数等实时状态信息。依据预处理机制，提出了基于最优任务分配方案的两种启发式算法：限制系数优先启发式算法和带宽优先启发式算法。实验数据表明本文提出的两种算法均优于Min-Min算法。
Along with the development of multi-core technology, the number of processing cores inthe processor has been increasing rapidly. In order to take full advantage of the huge amountof parallel computing resources, a highly efficient task scheduling mechanism is needed. Thispaper focuses on the research on key techniques of task scheduling based on multi-coredistributed environment, which has helped get to the shortest total execution time of theparallel tasks through reasonable scheduling tasks to each processing core.
Firstly, this paper elaborated on the structural characteristics of multi-core processorsfrom the development of multi-core processor structure and classification, and further studiedthe research status and problems of task scheduling that we’ve been facing under thedistributed environment. And then for static task scheduling, this paper proposed one taskscheduling algorithm for multi-core processors, and the other algorithm for multi-coreclusters; for dynamic task scheduling, this paper designed a dynamic load balancing modelbased on multi-core processors, and proposed a independent tasks scheduling algorithm ontree-based computing environments for heterogeneous multi-core clusters.
The main research work of this paper can be summarized as follows:
(1) This paper studied the problems of multi-task static scheduling based on theenvironment of a multi-core processor.
With the rapid growth of the quantity of processing cores in one processor, how toefficiently use these processing cores to get a minimum task execution time becomes the goalof task scheduling based on multi-core processors. In order to achieve this goal, the author hasbeen studying in two different aspects: How to reduce the communication cost among taskswhich were allocated to different processing cores; how to allocate tasks to improve theutilization of processing cores. This paper built a scheduling model based on the DAG, andthen proposed a task scheduling algorithm which combined task clustering with taskduplication technology. The algorithm includes three steps: firstly, changing task Graph fromDAG to in-tree graph; secondly according to in-tree graph, generating scheduling group or set;lastly adjusting scheduling set according to the number of processing cores. With taskreplication and clustering technology, the algorithm has reduced communication overheadamong tasks. Meanwhile the task completion time is kept a relatively lower value by using theload threshold, the load among cores is balanced and the utilization of processing cores isimproved. The time complexity of the algorithm is no more than several classical algorithms. Compared to genetic algorithm simulation experiment data shows that the proposed algorithmcan obtain near-optimal solutions in a relatively shorter time, and with the increasement ofcommunication overhead among tasks, the proposed algorithm shows a better performance.
(2) This paper studied the task scheduling problem for multi-core clusters.
With the architecture of high-performance general microprocessor into the multi-core era,multi-core processors have been increasingly used in cluster systems. Due to the introductionof multi-core processors, multi-core clusters include a two-level storage mechanism andthree-layer communication structure, which made the task scheduling problem for multi-coreclusters more complicated. In order to efficiently carry out the task allocation in a multi-corecluster, firstly, we built a task allocation model based on DAG, and then based on thetwo-level storage structure of multi-core clusters, this paper proposed a two-round taskscheduling algorithm, which scheduled tasks by level. According to the algorithm, theprocesses are assigned to processor nodes in the first round and the threads of processes areassigned to processing cores in the second round respectively. Towards three-layercommunication structure of multi-core clusters, in order to reduce the communicationoverhead, and achieve the earliest start time of current task, each round operation includestwo strategies: clustering strategy and adjust strategy. By reducing the inter-taskcommunication overhead， The algorithm minimizes the task scheduling length; Thealgorithm maintains load balancing between the two-level processing nodes by the loadthreshold, which improves the utilization of the processing core. Through comparison withrelated work, we can see that the time complexity of the algorithm is not more than similaralgorithms; three sets of comparative experiments show that the normalized schedule lengthof the proposed algorithm is less than the other two classic algorithms, and withCCR(communication to computation ratio) value being increased in DAG, the superiority ofthe proposed algorithm is prominent.
(3) This paper studied the five elements that affect the dynamic load balancing ofmulti-core processors.
Because dynamic load balancing algorithm can adapt to changes of nod loads, it is muchmore flexible and effective than static algorithm. However, dynamic algorithm will generatemore overhead than the static algorithm due to needs of collecting and analyzing stateinformation, but usually the cost is worthwhile. Based on the research on the problems of loadbalancing and scheduling for multiprocessors, according to the characteristics of CMP, wecarried out a detailed analysis of the various factors that affect the load balancing ofmulti-core processor. According to the above research, this paper proposes a formaldescription of a general model: utilizing a quintuple
(4) This paper studied the independent task dynamic scheduling problem forheterogeneous multi-core clusters.
The task scheduling mechanism based on homogeneous multi-core processor assignstasks to each processing core due to the number of tasks, but the task scheduling mechanismbased on heterogeneous multi-core assigned tasks to the processing cores which areappropriate for running the tasks according to the different properties of the task. The taskscheduling mechanism based on homogeneous multi-core processor assigns tasks to eachprocessing core due to the number of tasks, but the task scheduling mechanism based onheterogeneous multi-core assigned tasks to the processing cores which are appropriate forrunning the tasks according to the different properties of the task. Because processing core isheterogeneous, it increases the difficulty of the task scheduling. In this paper tree-basedmaster-slave model is applied to heterogeneous multi-core cluster, and each computing nodecorresponds to a processing core. This paper has researched and analyzed the classicindependent task scheduling problems and the master-slave tree-based computingenvironment, which built a pre-processing mechanism, through that we can gain the optimalnumber of tasks assigned to each core, real-time network communication ability among thecores and Real-time calculation ability of each processing core with load. Throughcomprehensive analyzing communication ability and calculation ability, we can obtainquantitative limit coefficient, which is used to evaluate the performance of the pros and consfor the target processing core. The paper proposed two heuristic algorithms based on theoptimal task scheduling scheme: a prior-limit-coefficient heuristic algorithm and aprior-bandwidth heuristic algorithm. Using the SimGrid platforms, this paper constructed andimplemented these two algorithms, and the experimental results show that the proposed twoalgorithms are better than Min-Min algorithm, and with the increasing number of tasks, theproposed algorithm shows more performance advantage than Min-Min algorithm.
引文
[1] R. R. Schaller. Moore's law: past, present and future[J]. Spectrum. IEEE.1997,34(6):52-59.
[2] Hennessy J L, Patterson D A. Computer Architecture: A quantitative approach[M].Morgan Kaufman Publishers,3rdedition,2002.
[3] Patterson D, Hennessy J. Computer Organization and Design: The Hardware/SoftwareInterface[M]. Fourth Edition. Morgan Kaufmann Publishers, Boston, MA, Nov.2008.
[4] Glenn Hinton. The Micro-architecture of the Pentium4Processor[J]. Intel TechnologyJournal, Q1,2001.
[5] Burger D, Goodman J R. Billion-Transistor Architectures：There and Back Again[J]. IEEEComputer,2004,37(3):22-28.
[6]黄立波.片上集群体系结构关键技术研究[D].《国防科学技术大学博士论文》.2010.10.
[7] Wayne Wolf. The future of multiproeessor systems-on-chips[C]. Pro of the41st AnnualConference on Design Automation. San Diego: ACM press,2004,681-684.
[8] Michael Creel, Willima L. Goffe. Multi-core CPUs, Clusters and Grid Computing[C]. aTutorial, Computing in Economics and Finance2005, Society for ComputationalEconomics.2005,238-245.
[9] Gepner, P. Kowalik, M.F. Multi-Core Processors: New Way to Achieve High SystemPerformance[C]. Parallel Computing in Electrical Engineering,2006. PAR ELEC2006,P9-13.
[10] STMieroeleetronics. Nomadik-open multimedia platform for next generation mobiledevices. httP://www.st.eom/stonline/Produets/literature/,2005-10-20.
[11] R. M. Ramanathan. Intel Multi-Core Processors: Leading the Next Digital Revolution,Technology@Intel Magazine
[12] Yingmin Li，Benjamin Leez, David Brooksz, Zhigang Huyy, Kevin Skadron. CMPDesign Space Exploration Subject to Physical Constraints[C].12thInternationalSymposium on High-Performance Computer Architecture.2006:17-28
[13] K. Olukotun, L. Hammond, J. Laudon. Chip multiprocessor architecture: techniques toimprove throughput and latency[M], Morgan&ClayPool,2007.
[14] Alfredo Buttari, Julien Langou, Jakub Kurzak, Jack Dongarra. A class of parallel tiledlinear algebra algorithms for multicore architectures[J]. Parallel Computing35(2009)38-53
[15] M. Listler, M. Perrone and F. Petrinl, Cell multiprocessor communication network: builtfor speed[J]. IEEE Micro,26(3),2-15,2006.
[16]陈芳园;张冬松;王志英.异构多核处理器体系结构设计研究[J].《计算机工程与科学》.2011,12
[17] K. Barker，K. D. Davis, A. Hoisie，D. Kerbyson, M.Lang，s.Pakin and J. C. Saneho.Experiences in scaling scientific applications on current generation quad-coreprocessors[C]. international symposium on parallel and distributed processing,1-8，2008.
[18] J. A. Kahle，M. N. Day，H. P. Hofstee，C. R. Johns，D. Shippy and T. R. Maeurer.Introduction to the cell multiprocessor[J]. IBM journal of research and development,49(4).589-604，2005.
[19] L. Hammond, B. A. Hubbert and M. Siu. The Stanford Hydra CMP[J]. IEEE Micro,20(2),71-84,2000.
[20] P. Kongetria, K. Aingaran and K. Olukotun. Niagara: a32-way multithreaded SParcproeessor[J]. IEEE Micro,25(2),21-29,2005.
[21] M. Shah，J. Barreh，J. Brooks and R. Golla. UltraSPARC12: A highly-threaded Powerefficient，SPARC SOC[C]. Asian solid-state circuits conference，22-25，2007.
[22] D. C. Pham, T. Aipperspach，D. Boerstler，M. Bolliger, R. Chaudhry and D. Cox.Overview of the architecture, circuit design and physical implementation of afirst-generation cell proeessor[J]. IEEE Iournal of solid-state circuits,41(1),179-196,2006.
[23] B. Sinharoy, Power7multi-core processor design[C], in42nd, annual IEEE/ACMInternational symposium on microarchitecture,1-8,2009.
[24] R. Kalla B. Sinharoy, W. J. Starke and M. Floyd. Power7: IBM next-generation serverproeessor[J].IEEE Micro,30(2),7-15,2010.
[25] D. M. Tullsen, S. J. Eggers and H. M. Levy, simultaneous multithreading: maximizingon-chip parallelisim[C]. In proceeding of22ndannual international symposium oncomputer architecture,392-403,1995.
[26] S. J. Eggers, J. S. Emer, H. M. Leby, J. L. Lo, R. L. Stamm and D. M. Tullsen.simultaneous multithreading: a platform for next generation processor[J]. IEEE Micro,17(5),12-19,1997.
[27]顾雄礼.片上多处理器关键技术研究[D].《浙江大学博士论文》.2011.06
[28] S. R. Vangal, J. Howard, G. Ruhl. An80-Tile Sub-100-W TeraFLOPS Processor in65-nm CMOS[J]. IEEE Journal of the Raw Microprocessor,43(1),2008,29-41,2008.
[29] M. B. Taylor. Evaluation of the Raw Microprocessor: An Exposed-Wire-DelayArchitecture for ILP and Streams[C]. In proeeeding of lnternational Symposium onComputer Architecture(ISCA04),2-13,2004.
[30]叶敏娇. Manticore体系结构设计[D].《浙江大学硕士论文》.2006.05
[31] Dac Pham et al. The Design and Implementation of a First Generation CELLProcessor[C]. Proceedings of the IEEE International Solid-State Circuits Conference,2005
[32]覃中.基于多核系统的线程调度.《电子科技大学硕士论文》.2009-04
[33] Musoll, E. A Thermal-Friendly Load-Balancing Technique for Multi-CoreProcessors[C].Quality Electronic Design,2008. ISQED2008.549-552
[34] O.Sinnen and L.Sousa. List Scheduling:Extension for Contention Awareness andEvaluation of Node Priorities for Heterogeneous Cluster Architectures[J]. ParallelComputing,30(1),81-101, Jan.2004.
[35] H. Topcuouglu, S. Hariri, Min-you Wu. Performance-Effective and Low-ComplexityTask Scheduling for Heterogeneous Computing[J]. IEEE Transactions on Parallel andDistributed Systems.13(3), March2002.
[36] Davidovi, T, Liberti, L., Maculan, N., Mladenovi,N., Mathematical Programming-BasedApproach to Scheduling Communicating Tasks, GERAD Tech. Report, G-2004-99.
[37]章军.分布式内存多处理机上并行任务静态调度[D].中国科学院博士学位论文.1999.
[38]支青，蒋昌俊．一种适于异构环境的任务调度算法[J]．自动化学报，2005，31(6)：865-872.
[39] D.Thain,T.Tannenbaum,M.Livny.Distributed Computing in Practice:The CondorExperience, Concurrency and Computation: Practice and Experience[J],2005,17(4):323-356.
[40] P.B.Bhat. Communication Scheduling Techniques for Distributed HeterogeneousSystems[D]. PhD thesis. University of Southern California. August1999.
[41] H.E.Rewini, G.T.Lewis, Distributed and Parallel Computing, Managing Publications.Greenwich. CT,1998.
[42] D.F.Baca.Allocating modules to processors in a distributed system[J]. IEEE Transactionson Software Engineering,1989,15(11):1427-1436.
[43] T.Bandyopadhyay, S.Basak, S.Bhattacharya. Multiprocessor scheduling algorithm fortasks with precedence relation[C].2004IEEE region10conference,2004,Vol2:164-167.
[44] Z.Jinquan, N.Lina, J.Changjun. A Heuristic Scheduling Strategy for Independent Taskson Grid[C]. Proceedings of the Eighth International Conference on High-PerformanceComputing in Asia-Pacific Region,2005,321-340.
[45] Madhukar,M.,Leuze,M.,and Dowdy,L. Petri net model of a dynamically partitionedmultiprocessors system[C], Proceedings of the Sixth International Workshop on PetriNets and Performance Models,73-82, October3-61995.
[46] A.Mihal,K.Keutzer,A.Jantsch,H.Tenhunen. Mapping Concurrent Applications ontoArchitectural Platforms[C].3,39-59, Kluwer Academic Publishers,2003.
[47] C.H.Papadimitriou and M.Yannakakis. Scheduling Interval-Ordered Tasks[J]. SIAMJournal on Computing,8,1979,405-409.
[48] C.J.Luan, G.H.Song, Y.Zheng. Application-adaptive resource scheduling in acomputational grid[J]. Journal of Zhejiang University SCIENCE A,2006,7(10):1634-1641.
[49] M.R.Garey and D.S.Johnson. Computers and Intractability: A Guide to the Theory of NPCompleteness, W.H.Freeman and Company,1979.
[50] Bernhard Thomaszewskia, Simon Pabsta, Wolfgang Blochingerb. Parallel techniques forphysically based simulation on multi-core processor architectures[C]. Computers&Graphics.32(1), February2008,25–40.
[51] Dummler, J., Rauber,T., Runger, G. Mapping Algorithms for Multiprocessor Tasks onMulti-core Clusters[C]. In: Parallel Processing,2008. ICPP'08.37th InternationalConference.
[52] Kumar, R. Zyuban, V.; Tullsen, D.M.. Interconnections in multi-core architectures:understanding mechanisms, overheads and scaling[C]. Computer Architecture,2005.ISCA '05. Proceedings.32nd International Symposium.408-419.
[53] Behrooz A. Shirazi, Krishna M. Kavi, Ali R. Hurson. Scheduling and Load Balancing inParallel and Distributed Systems[M]. IEEE Computer Society Press Los Alamitos, CA,USA,1995
[54]吴佳俊.多核多线程处理器上任务调度技术研究[D].中国科学院计算技术研究所[博士学位论文]，2006.04．
[55] T.C.Hu. Parallel Sequencing and Assembly Line Problems. Operations Research,19(6),Nov.1961,841-848.
[56] El-Rewini, H. Ali, H.H.; Lewis, T. Task scheduling in multiprocessing systems[J].Computer.28(12), Dec,1995,27-37
[57] RAMAMOORTHY,C.V.,CHANDY,K.M.,AND GONZA-LEZ,M.J. Optimal schedulingstrategies in a multiprocessor system[C]. IEEE Trans. Computer21(2),137-146.1972.
[58] E.G.Coffman and R.L.Graham. Optimal Scheduling for Two-Processor Systems. ActaInformatica, vol.1,1972,200-213.
[59] R.Sethi. Scheduling Graphs on Two Processors[J]. SIAM Journal on Computing,5(1),Mar.1976,73-82.
[60] J.Ullman. NP-Complete Scheduling Problems[J]. Journal of Computer and SystemSciences,10,1975,384-393.
[61] H.El-Rewini,T.G.Lewis. Scheduling Parallel Programs onto Arbitrary TargetMachines[J]. Parallel and Distributed Computing,1990,9(2):138~153
[62] Michael A.Palis, Jing-Chiou Liou, David S.L.Wei. Task Clustering and Scheduling forDistributed Memory Parallel Architectures[C].IEEE Trans.on Parallel and DistributedSystems,1996,7(1):46~55
[63] Mitehell M. An Introduction to Genetic Algorithms[M].Cambrige，MA:The MIT Press，1996.
[64] Fibich,P., Matyska,L., Rudova,H. Model of Grid Scheduling Problem[M].In ExploringPlanning and Scheduling for Web Services, Grid and Autonomic Computing. MenloPark, California, USA: AAAI Press,2005.
[65] V.Sarkar. Partitioning and Scheduling of Parallel Programs for Multiprocessors[C].Research Monographs in Parallel Computing, MIT Press,1989,564-573.
[66] Yang and A.Gerasoulis. DSC:Scheduling Parallel Tasks on an Unbounded Number ofProcessors[C]. IEEE Trans.Parallel Distributed System, Sep1994.314-325.
[67] Thomas L.Adam,K.Mani Chandy, JR Dickson. A Comparison of List Schedules forParallel Processing Systems[C]. for Parallel Processing Systems. CACM17(12):685-690(1974).
[68] Ahmad, I.Yu-Kwong Kwok. A New Approach to Scheduling Parallel Programs UsingTask Duplication[C].Parallel Processing,1994. ICPP1994.47-51.
[69] Y.Kwok and I.Ahmad. Benchmarking the Task Graph Scheduling Algorithms[C].Proceedings of International Parallel Processing Symposium, Florida, U.S.A. April1998,531-537.
[70]刘振英，方滨兴，姜誉，张毅，赵宏.一个调度Fork-Join任务图的新算法.软件学报，2002，13(4)：693-697.
[71] Darbha,S., Agrawal,D.P. Optimal scheduling algorithm for distributed-memorymachines[C]. IEEE Transactions on Parallel and Distributed Systems,1998,9(1):87~95.
[72] C.H.Papadimitriou and M.Yannakakis. Towards an Architecture-Independent Analysisof Parallel Algorithms[J]. SIAM journal on Computing,19(2), Apr.1990,322-328.
[73] B.Kruatrachue and T.G.Lewis. Duplication Scheduling Heuristics(DSH):A NewPrecedence Task Scheduler for Parallel Processor Systems. Technical Report, OregonState University, Corvallis, OR97331,1987.
[74] Rashmi Bajaj and Dharma P.Agrawal. Improving Scheduling of Tasks in aHeterogeneous Environment[J]. IEEE Trans.on parallel and distributed systems,15(2),February2004.
[75] Pasham,S.,WM.Lin. Efficient task scheduling with duplication for bounded number ofprocessors[C]. Proceedings.11th International Conference on Volume1,20-22July2005543-549.
[76] Hagras T, Janecek.A. high performance, low complexity algorithm for compile-time taskscheduling in heterogeneous sys-tem[C]. Parallel Computing.2005,578-580.
[77] J.Y.Colin and P.Chretienne. C.P.M Scheduling with Small Computation Delays and TaskDuplication [C]. Operation Research,1991,680-684.
[78]赵磊.适应多核处理器的任务调度研究.《哈尔滨理工大学硕士论文》.2010-03
[79] Y. Liu, X. Zhang, H. Li, and D. Qian. Allocating Tasks in Multi-core Processor basedParallel Systems[C]. In2007IFIP International Conference on Network and ParallelComputing Workshops (NPC2007),2007.
[80] kira Hatanaka and Nader Bagherzadeh, Scheduling Techniques for Multi-CoreArchitectures[C].2009Sixth International Conference on Information Technology: NewGenerations,2009,865-870
[81] Liang-Teh Lee, Huang-Yuan Chang, and Shu-Wei Chao. A Hybrid Task Scheduling forMulti-Core Platform[C].2008Second International Conference on Future GenerationCommunication and Networking Symposia,2008,40-45.
[82] Ahmad, I., S. Ranka,,S.U. Khan.Using game theory for scheduling tasks on multi-coreprocessors for simultaneous optimization of performance and energy[C]. Parallel andDistributed Processing.2008,56-72.
[83] V. Sarkar IBM Research, Thomas. J. et.al..Instruction reordering for fork-joinparallelism[C]. PLDI '90Proceedings of the ACM SIGPLAN1990conference onProgramming language design and implementation.322-336,1990
[84] V.Kianzad and S.S.Bhattacharyya. A Comparison of Clustering and SchedulingTechniques for Embedded Multiprocessor Systems. Technical ReportUMIACS-TR-2003-114,Institute for Advanced Computer Studies, University ofMaryland at College Park,December2003.
[85] Xiaozhong Geng, Gaochao Xu, Xiaodong Fu, Yuan Zhang. A task scheduling algorithmfor multi-core-cluster systems[J]. Journal of Computers (Finland), v7, n11, p2797-2804,2012.
[86] I.Ahmad and Y.Kwok,“On Parallelizing the Multiprocessor Scheduling Problem,”IEEETransactions on Parallel and Distributed Systems[J],10(4),414-432, April1999.
[87] M.A.Al-Mouhamed. Lower Bound on the Number of Processors and Time forScheduling Precedence Graphs with Communication Costs[J]. IEEE Trans. SoftwareEngineering,16(12),1390-1401, Dec.1990.
[88] N.G.Hall and M.E.Posner. Generating experimental data for computational testing withmachine seheduling applications[J]. Operations Research49:854-865,2001.
[89] C.L.McCreary,A.A.Khan,J.J.Thompson,and M.E.McArdle. A comparison of heuristicsfor scheduling DAGS on multiprocessors[C]. in Proc.of the Int.Parallel ProcessingSymp,1994,446-451.
[90] R.Buyya. High Performance Cluster Cluster Computing: Architectures and systems.Upper Saddle River, NJ, USA:Prentice Hall PTR,1999.
[91] P Vignesh T. RaviGagan Agrawal. erformance Issues in Parallelizing Data-IntensiveApplications on a Multi-core Cluster[C]. CCGRID '09Proceedings of the20099thIEEE/ACM International Symposium on Cluster Computing and the GridPages308-315.
[92] Zhou Shuang-E, Yuan You-Guang, Xiong Bing-Zhou, Ou Zhong-Hong. An algorithm ofprocessor pre-allocation based on task duplication[J]. Chinese Journal of Computers,2004,27(2):216-223.
[93] Li Min, Wang Hui, Li Ping. Tasks mapping in multi-core based system: hybridACO&GA approach [C]. Proc of the5th Int Conf on ASIC. Piscataway, NJ: IEEE,2003.
[94]刘轶,张听,李鹤.一种面向多核处理器并行系统的启发式任务分配算法[J].计算机研究与发展,2009,46(6):1058-1064.
[95] YUAN Yun, SHAO Shi, Tasks scheduling algorithm for parallel system with multi-coreprocessor[J]. Computer Applications,2008,28(12),280-283.
[96] Ennals R, Sharp R, Mycroft A. Task partitioning for multi-core network processors [C].Proc of the14th Int Conf on Compiler Construction. Berlin: Springer,2005
[97] H. Chen, W. Chen, J. Huang, B. Robert, and H. Kuhn. Mpipp: an automaticprofile-guided parallel process placement toolset for smp clusters and multiclusters[C].In ICS '06: Proc. of the20th Int. Conf. on Supercomputing,353-360, New York, NY,USA,2006. ACM.
[98] Tsuchiya, T., Osada, T. Kikuno, T. A new heuristic algorithm based on GAs formultiprocessor scheduling with task duplication[C]. Algorithms and Architectures forParallel Processing,1997. ICAPP97,19973rd International Conference.
[99] Gerasoulis A, Yang T. A Comparison of Clustering Heuristics for Scheduling DAGs onMultiprocessors[J]. Journal of Parallel and Distributed Computing, Dec.1992,16:276-291.
[100] Edwin S H, Nirwan Ansari, HongRen. A Genetic Algorithm for MultiproeessorSeheduling[J]. IEEE Transactions On Parallel And Distributed Systems.1994,5(2):113-120.
[101] Bansal S, Kumar P, Singh K. An improved two-step algorithm for task and data parallelscheduling in distributed memory machines [J]. Parallel Computing,2006,32(10):759-774.
[102] Rabenseifner, R. Hager, G.; Jost, G. Hybrid MPI/OpenMP Parallel Programming onClusters of Multi-Core SMP Nodes[C].Parallel, Distributed and Network-basedProcessing,200917th Euromicro International Conference.427-436.
[103] LAN Zhou, SUN Shi-Xin. An Algorithm of Allocating Tasks to Multiprocessors Basedon Dynamic Critical Task, journal of computers,2007,30(3):454-461.
[104]李冬梅,施海虎.负载平衡调度问题的一般模型研究[J].计算机工程与应用.2007，43(8):PP121-125.
[105]王群霞.基于集群的不确定因素下的动态负载平衡[D].《浙江师范大学硕士论文》.2007-12.
[106]马雪洁;邓可.网络机群计算的负载指标研究与实胡凯[J].《计算机工程与设计》,2007-02.
[107] Marc H,Willebeek-L M.Strategies for dynamic load balancing on highly parallelcomputers[J]. IEEE Transactions on Parallel and DistributedSystem,1993,4(9):979-993.
[108] S. Y. Borkar, P. Dubey, K. C. Kahn, D. J. Kuck, H. Mulder,S. S. Pawlowski, and J.Rattner. Platform2015: Intel processor and platform evolution for the next decade.White Paper, Intel Corporation,2005.
[109]牛雪征.分布式计算机系统动态负载平衡的研究[D].《南京航空航天大学硕士论文》.2003-01.
[110] Kedar M. Katre, Harini Ramaprasad, Abhik Sarkar, Frank Mueller. Policies forMigration of Real-Time Tasks in Embedded Multi-Core Systems[J]. RTSS2009,30thIEEE Real-Time Systems Symposium,456-470.
[111]陈华平,计用昶,陈国良.分布式动态负载平衡调度的一个通用模型[J].软件学报,9(1),25-29,1998.
[112]徐高潮,鞠九滨,胡亮;分布式计算系统[M].2004.
[113] Hui Chi-Chung,Chanson S T.Hydrodynamic load balancing[J].IEEE Transactions onParallel and Distributed System,1999,10(11):1118-1137.
[114]鞠九滨,杨鲲,徐高潮.使用资源利用率作为负载平衡系统的负载指标[J].软件学报,1996,7(4):238-243.
[115]袁云.基于多核处理器并行系统的任务调度算法研究[D].《华东师范大学硕士论文》-2008-10
[116] Hau Yee Sit, Kei Shui Ho, HongVa Leong，Robert W.P.Luk，Lai Kuen Ho. AnAdaptive Clustering Approach to Dynamic Load Balancing[C]. Proeeeding of the7thinternational Symposium on Parallel Architectures, Algorithms and Networks,2004IEEE,245-258.
[117] Rodrigues, Eduardo R., Navaux, Philippe O. A., Panetta, Jairo et al. A comparativeanalysis of load balancing algorithms applied to aweather forecast model[C].Proceedings-22nd International Symposium on Computer Architecture and HighPerformance Computing, SBAC-PAD2010.71-78.
[118] Li Haisheng, Shi Hongyan, An adaptive load balancing algorithm based on discreteuniform distribution[J]. Advanced Materials Research, v108-111, n1,1392-1396,2010.
[119] Ferrari D,Zhou S. A load index for dynamic load balancing[C].1986Fall JointComputer Conference, Nov.1986.
[120] Bonomi F,Fleming P J,Steinberg P. An adaptive join-the-biased-queue rule for loadsharing on distributed computer system[C].28thConferece On Decision andControl,Dec.1989.
[121] Kunz T. The influence of different workload description on a heuristic load balancingscheme[C]. IEEE Transaction On Software Engineering,July1991,17(7).
[122] Banawan S A,ZahorjanJ.On comparing load indices using oracle simulation[C].1990Winter Simulation Conference,1990.
[123] Mehra P, Wah B W.Automatic learning of workload measures for load balancing on adistributed system[C]. Int’lConf. on Parallel Processing,1993.
[124] Wentao Wang, Xiaozhong Geng, Qing Wang. Design of a dynamic load balancingmodel for multiprocessor systems[C].2011IEEE3rd International Conference onCommunication Software and Networks, ICCSN2011,641-643,2011.
[125] Dhakal S，Hayat MM，Pezoa J E. Dynamic load balancing in distributed system in thePresence of delays: a regeneration-theory approach[J]. IEEE Transactions on Paralleland Distributed Systems,2007,18(4):485-497.
[126] Kruatrachce B, Lewis T. Grain size determination for parallel processing[C]. IEEESoftware,1998,1:23-32.
[127] Brinkley Sprunt. Aperiodic Task Scheduling for Real-Time Systems. Ph.D. Dissertation.1990.
[128] Xiaozhong Geng, Gaochao Xu, Yuan Zhang. Dynamic load balancing schedulingmodel based on multi-core processor[C]. The5th International Conference on Frontierof Computer Science and Technology, FCST2010, p398-403,2010.
[129] S.K.Baruah. Feasibility Analysis of Preemptive Real-time Systems UponHeterogeneous Multiprocessor Platforms[C]. Proceedings of the25thIEEE IntemationalReal-time Systems Symposium[C]，2004:37-46.
[130]王群霞.基于集群的不确定因素下的动态负载平衡[D].浙江师范大学硕士论文.2007.
[131] Wenmin Miao, Dongni Li, Wei Zhang. A load-balancing dynamic scheduling algorithmunder machine failure conditions[C].2010International Conference on IntelligentComputation Technology and Automation, ICICTA2010, v1,144-147,2010.
[132] Beaumont O, Carter L, Ferrante J, Legrand A, Robert Y. Bandwidth-centric allocationof independent tasks on heterogeneous platforms[C]. Parallel and DistributedProcessing Symposium, Proceedings International, IPDPS2002,67-72.
[133] P. F. Dutot. Master-slave Tasking on Heterogeneous Processors.In International Paralleland Distributed Processing Symposium[C], page25b. IEEE Computer Society Press,April2003.
[134] Banino, C.; Beaumont, O.; Carter, L.; Ferrante, J.;etc.al.Scheduling strategies formaster-slave tasking on heterogeneous processor platforms[J]. Parallel and DistributedSystems, IEEE Transactions. April2004.15(4)319-330.
[135] P Dutot.Complexity of master-slave tasking on heterogeneoustrees[J]．European Journalon Operational Research．2005,164(3)：690-695.
[136] O H Ibarra, C E Kim．Heuristic algorithms for scheduling independent tasks onnonidentical processor[J]．Journal of the ACM.1977,24(2):280-289．
[137]蒋建春,汪同庆．异构多核处理器的任务调度算法[J]．计算机工程与应用，2009,45(33):52-56.
[138] Olivier Beaumont．Vinent Boudet，Yves Robert．A realistic model and efficientheuristic for scheduling with heterogeneous processor[C]．Proceedings of the16thInternational Parallel and Distributed Processing Symposium,2002,37-49．
[139] Braun TD, Siegel HJ, Beck N. A comparison of eleven static heuristics for mapping aclass of independent tasks onto heterogeneous distributed computing systems[J].Journal of Parallel and Distributed Computing,2001,61(6):810837.
[140] Haluk Topcuoglu, Salim Hariri, Min-You Wu. Task Scheduling Algorithms forHeterogeneous Processors[C]. Proceedings of the Heterogeneous Computing Workshop,HCW,1999:3-14.
[141] SETI at home, URL: http://setiathome.ssl.berkeley.edu.
[142] Cyril Banino. A Distributed Procedure for Bandwidth-Centric Scheduling ofIndependent-Task Applications[J]. Parallel and Distributed Processing Symposium,[C]2005. Proceedings.19th IEEE International,2005:48a-48a.
[143] L.Wei-Wei. Independent Tasks Scheduling on Tree-Based Grid Computing Platforms[j].Journal of Software,200617(11):2352-2361.
[144] Karmarkar N. A new polynomial-time algorithm for linear programming[J].Combinatorica,1984,4(4):373-395.
[145] Emanuele Goldoni, Giuseppe Rossi, Alberto Torelli. Assolo, a New Method forAvailable Bandwidth Estimation[C].2009Fourth International Conference on InternetMonitoring and Protection.
[146]张晓杰，孟庆春，曲卫芬．基于蚁群优化算法的服务网格的作业调度［Ｊ］．计算机工程，2006,32(8):216-218.
[147]王历.基于树形网络的云计算环境下的任务调度策略[D].《吉林大学硕士论文》2012.7.
[148] Casanova, H. Legrand, A.; Quinson, M. SimGrid: A Generic Framework forLarge-Scale Distributed Experiments. Computer Modeling and Simulation,2008.UKSIM2008. Tenth International Conference126-131.
[2] Hennessy J L, Patterson D A. Computer Architecture: A quantitative approach[M].Morgan Kaufman Publishers,3rdedition,2002.
[3] Patterson D, Hennessy J. Computer Organization and Design: The Hardware/SoftwareInterface[M]. Fourth Edition. Morgan Kaufmann Publishers, Boston, MA, Nov.2008.
[4] Glenn Hinton. The Micro-architecture of the Pentium4Processor[J]. Intel TechnologyJournal, Q1,2001.
[5] Burger D, Goodman J R. Billion-Transistor Architectures：There and Back Again[J]. IEEEComputer,2004,37(3):22-28.
[6]黄立波.片上集群体系结构关键技术研究[D].《国防科学技术大学博士论文》.2010.10.
[7] Wayne Wolf. The future of multiproeessor systems-on-chips[C]. Pro of the41st AnnualConference on Design Automation. San Diego: ACM press,2004,681-684.
[8] Michael Creel, Willima L. Goffe. Multi-core CPUs, Clusters and Grid Computing[C]. aTutorial, Computing in Economics and Finance2005, Society for ComputationalEconomics.2005,238-245.
[9] Gepner, P. Kowalik, M.F. Multi-Core Processors: New Way to Achieve High SystemPerformance[C]. Parallel Computing in Electrical Engineering,2006. PAR ELEC2006,P9-13.
[10] STMieroeleetronics. Nomadik-open multimedia platform for next generation mobiledevices. httP://www.st.eom/stonline/Produets/literature/,2005-10-20.
[11] R. M. Ramanathan. Intel Multi-Core Processors: Leading the Next Digital Revolution,Technology@Intel Magazine
[12] Yingmin Li，Benjamin Leez, David Brooksz, Zhigang Huyy, Kevin Skadron. CMPDesign Space Exploration Subject to Physical Constraints[C].12thInternationalSymposium on High-Performance Computer Architecture.2006:17-28
[13] K. Olukotun, L. Hammond, J. Laudon. Chip multiprocessor architecture: techniques toimprove throughput and latency[M], Morgan&ClayPool,2007.
[14] Alfredo Buttari, Julien Langou, Jakub Kurzak, Jack Dongarra. A class of parallel tiledlinear algebra algorithms for multicore architectures[J]. Parallel Computing35(2009)38-53
[15] M. Listler, M. Perrone and F. Petrinl, Cell multiprocessor communication network: builtfor speed[J]. IEEE Micro,26(3),2-15,2006.
[16]陈芳园;张冬松;王志英.异构多核处理器体系结构设计研究[J].《计算机工程与科学》.2011,12
[17] K. Barker，K. D. Davis, A. Hoisie，D. Kerbyson, M.Lang，s.Pakin and J. C. Saneho.Experiences in scaling scientific applications on current generation quad-coreprocessors[C]. international symposium on parallel and distributed processing,1-8，2008.
[18] J. A. Kahle，M. N. Day，H. P. Hofstee，C. R. Johns，D. Shippy and T. R. Maeurer.Introduction to the cell multiprocessor[J]. IBM journal of research and development,49(4).589-604，2005.
[19] L. Hammond, B. A. Hubbert and M. Siu. The Stanford Hydra CMP[J]. IEEE Micro,20(2),71-84,2000.
[20] P. Kongetria, K. Aingaran and K. Olukotun. Niagara: a32-way multithreaded SParcproeessor[J]. IEEE Micro,25(2),21-29,2005.
[21] M. Shah，J. Barreh，J. Brooks and R. Golla. UltraSPARC12: A highly-threaded Powerefficient，SPARC SOC[C]. Asian solid-state circuits conference，22-25，2007.
[22] D. C. Pham, T. Aipperspach，D. Boerstler，M. Bolliger, R. Chaudhry and D. Cox.Overview of the architecture, circuit design and physical implementation of afirst-generation cell proeessor[J]. IEEE Iournal of solid-state circuits,41(1),179-196,2006.
[23] B. Sinharoy, Power7multi-core processor design[C], in42nd, annual IEEE/ACMInternational symposium on microarchitecture,1-8,2009.
[24] R. Kalla B. Sinharoy, W. J. Starke and M. Floyd. Power7: IBM next-generation serverproeessor[J].IEEE Micro,30(2),7-15,2010.
[25] D. M. Tullsen, S. J. Eggers and H. M. Levy, simultaneous multithreading: maximizingon-chip parallelisim[C]. In proceeding of22ndannual international symposium oncomputer architecture,392-403,1995.
[26] S. J. Eggers, J. S. Emer, H. M. Leby, J. L. Lo, R. L. Stamm and D. M. Tullsen.simultaneous multithreading: a platform for next generation processor[J]. IEEE Micro,17(5),12-19,1997.
[27]顾雄礼.片上多处理器关键技术研究[D].《浙江大学博士论文》.2011.06
[28] S. R. Vangal, J. Howard, G. Ruhl. An80-Tile Sub-100-W TeraFLOPS Processor in65-nm CMOS[J]. IEEE Journal of the Raw Microprocessor,43(1),2008,29-41,2008.
[29] M. B. Taylor. Evaluation of the Raw Microprocessor: An Exposed-Wire-DelayArchitecture for ILP and Streams[C]. In proeeeding of lnternational Symposium onComputer Architecture(ISCA04),2-13,2004.
[30]叶敏娇. Manticore体系结构设计[D].《浙江大学硕士论文》.2006.05
[31] Dac Pham et al. The Design and Implementation of a First Generation CELLProcessor[C]. Proceedings of the IEEE International Solid-State Circuits Conference,2005
[32]覃中.基于多核系统的线程调度.《电子科技大学硕士论文》.2009-04
[33] Musoll, E. A Thermal-Friendly Load-Balancing Technique for Multi-CoreProcessors[C].Quality Electronic Design,2008. ISQED2008.549-552
[34] O.Sinnen and L.Sousa. List Scheduling:Extension for Contention Awareness andEvaluation of Node Priorities for Heterogeneous Cluster Architectures[J]. ParallelComputing,30(1),81-101, Jan.2004.
[35] H. Topcuouglu, S. Hariri, Min-you Wu. Performance-Effective and Low-ComplexityTask Scheduling for Heterogeneous Computing[J]. IEEE Transactions on Parallel andDistributed Systems.13(3), March2002.
[36] Davidovi, T, Liberti, L., Maculan, N., Mladenovi,N., Mathematical Programming-BasedApproach to Scheduling Communicating Tasks, GERAD Tech. Report, G-2004-99.
[37]章军.分布式内存多处理机上并行任务静态调度[D].中国科学院博士学位论文.1999.
[38]支青，蒋昌俊．一种适于异构环境的任务调度算法[J]．自动化学报，2005，31(6)：865-872.
[39] D.Thain,T.Tannenbaum,M.Livny.Distributed Computing in Practice:The CondorExperience, Concurrency and Computation: Practice and Experience[J],2005,17(4):323-356.
[40] P.B.Bhat. Communication Scheduling Techniques for Distributed HeterogeneousSystems[D]. PhD thesis. University of Southern California. August1999.
[41] H.E.Rewini, G.T.Lewis, Distributed and Parallel Computing, Managing Publications.Greenwich. CT,1998.
[42] D.F.Baca.Allocating modules to processors in a distributed system[J]. IEEE Transactionson Software Engineering,1989,15(11):1427-1436.
[43] T.Bandyopadhyay, S.Basak, S.Bhattacharya. Multiprocessor scheduling algorithm fortasks with precedence relation[C].2004IEEE region10conference,2004,Vol2:164-167.
[44] Z.Jinquan, N.Lina, J.Changjun. A Heuristic Scheduling Strategy for Independent Taskson Grid[C]. Proceedings of the Eighth International Conference on High-PerformanceComputing in Asia-Pacific Region,2005,321-340.
[45] Madhukar,M.,Leuze,M.,and Dowdy,L. Petri net model of a dynamically partitionedmultiprocessors system[C], Proceedings of the Sixth International Workshop on PetriNets and Performance Models,73-82, October3-61995.
[46] A.Mihal,K.Keutzer,A.Jantsch,H.Tenhunen. Mapping Concurrent Applications ontoArchitectural Platforms[C].3,39-59, Kluwer Academic Publishers,2003.
[47] C.H.Papadimitriou and M.Yannakakis. Scheduling Interval-Ordered Tasks[J]. SIAMJournal on Computing,8,1979,405-409.
[48] C.J.Luan, G.H.Song, Y.Zheng. Application-adaptive resource scheduling in acomputational grid[J]. Journal of Zhejiang University SCIENCE A,2006,7(10):1634-1641.
[49] M.R.Garey and D.S.Johnson. Computers and Intractability: A Guide to the Theory of NPCompleteness, W.H.Freeman and Company,1979.
[50] Bernhard Thomaszewskia, Simon Pabsta, Wolfgang Blochingerb. Parallel techniques forphysically based simulation on multi-core processor architectures[C]. Computers&Graphics.32(1), February2008,25–40.
[51] Dummler, J., Rauber,T., Runger, G. Mapping Algorithms for Multiprocessor Tasks onMulti-core Clusters[C]. In: Parallel Processing,2008. ICPP'08.37th InternationalConference.
[52] Kumar, R. Zyuban, V.; Tullsen, D.M.. Interconnections in multi-core architectures:understanding mechanisms, overheads and scaling[C]. Computer Architecture,2005.ISCA '05. Proceedings.32nd International Symposium.408-419.
[53] Behrooz A. Shirazi, Krishna M. Kavi, Ali R. Hurson. Scheduling and Load Balancing inParallel and Distributed Systems[M]. IEEE Computer Society Press Los Alamitos, CA,USA,1995
[54]吴佳俊.多核多线程处理器上任务调度技术研究[D].中国科学院计算技术研究所[博士学位论文]，2006.04．
[55] T.C.Hu. Parallel Sequencing and Assembly Line Problems. Operations Research,19(6),Nov.1961,841-848.
[56] El-Rewini, H. Ali, H.H.; Lewis, T. Task scheduling in multiprocessing systems[J].Computer.28(12), Dec,1995,27-37
[57] RAMAMOORTHY,C.V.,CHANDY,K.M.,AND GONZA-LEZ,M.J. Optimal schedulingstrategies in a multiprocessor system[C]. IEEE Trans. Computer21(2),137-146.1972.
[58] E.G.Coffman and R.L.Graham. Optimal Scheduling for Two-Processor Systems. ActaInformatica, vol.1,1972,200-213.
[59] R.Sethi. Scheduling Graphs on Two Processors[J]. SIAM Journal on Computing,5(1),Mar.1976,73-82.
[60] J.Ullman. NP-Complete Scheduling Problems[J]. Journal of Computer and SystemSciences,10,1975,384-393.
[61] H.El-Rewini,T.G.Lewis. Scheduling Parallel Programs onto Arbitrary TargetMachines[J]. Parallel and Distributed Computing,1990,9(2):138~153
[62] Michael A.Palis, Jing-Chiou Liou, David S.L.Wei. Task Clustering and Scheduling forDistributed Memory Parallel Architectures[C].IEEE Trans.on Parallel and DistributedSystems,1996,7(1):46~55
[63] Mitehell M. An Introduction to Genetic Algorithms[M].Cambrige，MA:The MIT Press，1996.
[64] Fibich,P., Matyska,L., Rudova,H. Model of Grid Scheduling Problem[M].In ExploringPlanning and Scheduling for Web Services, Grid and Autonomic Computing. MenloPark, California, USA: AAAI Press,2005.
[65] V.Sarkar. Partitioning and Scheduling of Parallel Programs for Multiprocessors[C].Research Monographs in Parallel Computing, MIT Press,1989,564-573.
[66] Yang and A.Gerasoulis. DSC:Scheduling Parallel Tasks on an Unbounded Number ofProcessors[C]. IEEE Trans.Parallel Distributed System, Sep1994.314-325.
[67] Thomas L.Adam,K.Mani Chandy, JR Dickson. A Comparison of List Schedules forParallel Processing Systems[C]. for Parallel Processing Systems. CACM17(12):685-690(1974).
[68] Ahmad, I.Yu-Kwong Kwok. A New Approach to Scheduling Parallel Programs UsingTask Duplication[C].Parallel Processing,1994. ICPP1994.47-51.
[69] Y.Kwok and I.Ahmad. Benchmarking the Task Graph Scheduling Algorithms[C].Proceedings of International Parallel Processing Symposium, Florida, U.S.A. April1998,531-537.
[70]刘振英，方滨兴，姜誉，张毅，赵宏.一个调度Fork-Join任务图的新算法.软件学报，2002，13(4)：693-697.
[71] Darbha,S., Agrawal,D.P. Optimal scheduling algorithm for distributed-memorymachines[C]. IEEE Transactions on Parallel and Distributed Systems,1998,9(1):87~95.
[72] C.H.Papadimitriou and M.Yannakakis. Towards an Architecture-Independent Analysisof Parallel Algorithms[J]. SIAM journal on Computing,19(2), Apr.1990,322-328.
[73] B.Kruatrachue and T.G.Lewis. Duplication Scheduling Heuristics(DSH):A NewPrecedence Task Scheduler for Parallel Processor Systems. Technical Report, OregonState University, Corvallis, OR97331,1987.
[74] Rashmi Bajaj and Dharma P.Agrawal. Improving Scheduling of Tasks in aHeterogeneous Environment[J]. IEEE Trans.on parallel and distributed systems,15(2),February2004.
[75] Pasham,S.,WM.Lin. Efficient task scheduling with duplication for bounded number ofprocessors[C]. Proceedings.11th International Conference on Volume1,20-22July2005543-549.
[76] Hagras T, Janecek.A. high performance, low complexity algorithm for compile-time taskscheduling in heterogeneous sys-tem[C]. Parallel Computing.2005,578-580.
[77] J.Y.Colin and P.Chretienne. C.P.M Scheduling with Small Computation Delays and TaskDuplication [C]. Operation Research,1991,680-684.
[78]赵磊.适应多核处理器的任务调度研究.《哈尔滨理工大学硕士论文》.2010-03
[79] Y. Liu, X. Zhang, H. Li, and D. Qian. Allocating Tasks in Multi-core Processor basedParallel Systems[C]. In2007IFIP International Conference on Network and ParallelComputing Workshops (NPC2007),2007.
[80] kira Hatanaka and Nader Bagherzadeh, Scheduling Techniques for Multi-CoreArchitectures[C].2009Sixth International Conference on Information Technology: NewGenerations,2009,865-870
[81] Liang-Teh Lee, Huang-Yuan Chang, and Shu-Wei Chao. A Hybrid Task Scheduling forMulti-Core Platform[C].2008Second International Conference on Future GenerationCommunication and Networking Symposia,2008,40-45.
[82] Ahmad, I., S. Ranka,,S.U. Khan.Using game theory for scheduling tasks on multi-coreprocessors for simultaneous optimization of performance and energy[C]. Parallel andDistributed Processing.2008,56-72.
[83] V. Sarkar IBM Research, Thomas. J. et.al..Instruction reordering for fork-joinparallelism[C]. PLDI '90Proceedings of the ACM SIGPLAN1990conference onProgramming language design and implementation.322-336,1990
[84] V.Kianzad and S.S.Bhattacharyya. A Comparison of Clustering and SchedulingTechniques for Embedded Multiprocessor Systems. Technical ReportUMIACS-TR-2003-114,Institute for Advanced Computer Studies, University ofMaryland at College Park,December2003.
[85] Xiaozhong Geng, Gaochao Xu, Xiaodong Fu, Yuan Zhang. A task scheduling algorithmfor multi-core-cluster systems[J]. Journal of Computers (Finland), v7, n11, p2797-2804,2012.
[86] I.Ahmad and Y.Kwok,“On Parallelizing the Multiprocessor Scheduling Problem,”IEEETransactions on Parallel and Distributed Systems[J],10(4),414-432, April1999.
[87] M.A.Al-Mouhamed. Lower Bound on the Number of Processors and Time forScheduling Precedence Graphs with Communication Costs[J]. IEEE Trans. SoftwareEngineering,16(12),1390-1401, Dec.1990.
[88] N.G.Hall and M.E.Posner. Generating experimental data for computational testing withmachine seheduling applications[J]. Operations Research49:854-865,2001.
[89] C.L.McCreary,A.A.Khan,J.J.Thompson,and M.E.McArdle. A comparison of heuristicsfor scheduling DAGS on multiprocessors[C]. in Proc.of the Int.Parallel ProcessingSymp,1994,446-451.
[90] R.Buyya. High Performance Cluster Cluster Computing: Architectures and systems.Upper Saddle River, NJ, USA:Prentice Hall PTR,1999.
[91] P Vignesh T. RaviGagan Agrawal. erformance Issues in Parallelizing Data-IntensiveApplications on a Multi-core Cluster[C]. CCGRID '09Proceedings of the20099thIEEE/ACM International Symposium on Cluster Computing and the GridPages308-315.
[92] Zhou Shuang-E, Yuan You-Guang, Xiong Bing-Zhou, Ou Zhong-Hong. An algorithm ofprocessor pre-allocation based on task duplication[J]. Chinese Journal of Computers,2004,27(2):216-223.
[93] Li Min, Wang Hui, Li Ping. Tasks mapping in multi-core based system: hybridACO&GA approach [C]. Proc of the5th Int Conf on ASIC. Piscataway, NJ: IEEE,2003.
[94]刘轶,张听,李鹤.一种面向多核处理器并行系统的启发式任务分配算法[J].计算机研究与发展,2009,46(6):1058-1064.
[95] YUAN Yun, SHAO Shi, Tasks scheduling algorithm for parallel system with multi-coreprocessor[J]. Computer Applications,2008,28(12),280-283.
[96] Ennals R, Sharp R, Mycroft A. Task partitioning for multi-core network processors [C].Proc of the14th Int Conf on Compiler Construction. Berlin: Springer,2005
[97] H. Chen, W. Chen, J. Huang, B. Robert, and H. Kuhn. Mpipp: an automaticprofile-guided parallel process placement toolset for smp clusters and multiclusters[C].In ICS '06: Proc. of the20th Int. Conf. on Supercomputing,353-360, New York, NY,USA,2006. ACM.
[98] Tsuchiya, T., Osada, T. Kikuno, T. A new heuristic algorithm based on GAs formultiprocessor scheduling with task duplication[C]. Algorithms and Architectures forParallel Processing,1997. ICAPP97,19973rd International Conference.
[99] Gerasoulis A, Yang T. A Comparison of Clustering Heuristics for Scheduling DAGs onMultiprocessors[J]. Journal of Parallel and Distributed Computing, Dec.1992,16:276-291.
[100] Edwin S H, Nirwan Ansari, HongRen. A Genetic Algorithm for MultiproeessorSeheduling[J]. IEEE Transactions On Parallel And Distributed Systems.1994,5(2):113-120.
[101] Bansal S, Kumar P, Singh K. An improved two-step algorithm for task and data parallelscheduling in distributed memory machines [J]. Parallel Computing,2006,32(10):759-774.
[102] Rabenseifner, R. Hager, G.; Jost, G. Hybrid MPI/OpenMP Parallel Programming onClusters of Multi-Core SMP Nodes[C].Parallel, Distributed and Network-basedProcessing,200917th Euromicro International Conference.427-436.
[103] LAN Zhou, SUN Shi-Xin. An Algorithm of Allocating Tasks to Multiprocessors Basedon Dynamic Critical Task, journal of computers,2007,30(3):454-461.
[104]李冬梅,施海虎.负载平衡调度问题的一般模型研究[J].计算机工程与应用.2007，43(8):PP121-125.
[105]王群霞.基于集群的不确定因素下的动态负载平衡[D].《浙江师范大学硕士论文》.2007-12.
[106]马雪洁;邓可.网络机群计算的负载指标研究与实胡凯[J].《计算机工程与设计》,2007-02.
[107] Marc H,Willebeek-L M.Strategies for dynamic load balancing on highly parallelcomputers[J]. IEEE Transactions on Parallel and DistributedSystem,1993,4(9):979-993.
[108] S. Y. Borkar, P. Dubey, K. C. Kahn, D. J. Kuck, H. Mulder,S. S. Pawlowski, and J.Rattner. Platform2015: Intel processor and platform evolution for the next decade.White Paper, Intel Corporation,2005.
[109]牛雪征.分布式计算机系统动态负载平衡的研究[D].《南京航空航天大学硕士论文》.2003-01.
[110] Kedar M. Katre, Harini Ramaprasad, Abhik Sarkar, Frank Mueller. Policies forMigration of Real-Time Tasks in Embedded Multi-Core Systems[J]. RTSS2009,30thIEEE Real-Time Systems Symposium,456-470.
[111]陈华平,计用昶,陈国良.分布式动态负载平衡调度的一个通用模型[J].软件学报,9(1),25-29,1998.
[112]徐高潮,鞠九滨,胡亮;分布式计算系统[M].2004.
[113] Hui Chi-Chung,Chanson S T.Hydrodynamic load balancing[J].IEEE Transactions onParallel and Distributed System,1999,10(11):1118-1137.
[114]鞠九滨,杨鲲,徐高潮.使用资源利用率作为负载平衡系统的负载指标[J].软件学报,1996,7(4):238-243.
[115]袁云.基于多核处理器并行系统的任务调度算法研究[D].《华东师范大学硕士论文》-2008-10
[116] Hau Yee Sit, Kei Shui Ho, HongVa Leong，Robert W.P.Luk，Lai Kuen Ho. AnAdaptive Clustering Approach to Dynamic Load Balancing[C]. Proeeeding of the7thinternational Symposium on Parallel Architectures, Algorithms and Networks,2004IEEE,245-258.
[117] Rodrigues, Eduardo R., Navaux, Philippe O. A., Panetta, Jairo et al. A comparativeanalysis of load balancing algorithms applied to aweather forecast model[C].Proceedings-22nd International Symposium on Computer Architecture and HighPerformance Computing, SBAC-PAD2010.71-78.
[118] Li Haisheng, Shi Hongyan, An adaptive load balancing algorithm based on discreteuniform distribution[J]. Advanced Materials Research, v108-111, n1,1392-1396,2010.
[119] Ferrari D,Zhou S. A load index for dynamic load balancing[C].1986Fall JointComputer Conference, Nov.1986.
[120] Bonomi F,Fleming P J,Steinberg P. An adaptive join-the-biased-queue rule for loadsharing on distributed computer system[C].28thConferece On Decision andControl,Dec.1989.
[121] Kunz T. The influence of different workload description on a heuristic load balancingscheme[C]. IEEE Transaction On Software Engineering,July1991,17(7).
[122] Banawan S A,ZahorjanJ.On comparing load indices using oracle simulation[C].1990Winter Simulation Conference,1990.
[123] Mehra P, Wah B W.Automatic learning of workload measures for load balancing on adistributed system[C]. Int’lConf. on Parallel Processing,1993.
[124] Wentao Wang, Xiaozhong Geng, Qing Wang. Design of a dynamic load balancingmodel for multiprocessor systems[C].2011IEEE3rd International Conference onCommunication Software and Networks, ICCSN2011,641-643,2011.
[125] Dhakal S，Hayat MM，Pezoa J E. Dynamic load balancing in distributed system in thePresence of delays: a regeneration-theory approach[J]. IEEE Transactions on Paralleland Distributed Systems,2007,18(4):485-497.
[126] Kruatrachce B, Lewis T. Grain size determination for parallel processing[C]. IEEESoftware,1998,1:23-32.
[127] Brinkley Sprunt. Aperiodic Task Scheduling for Real-Time Systems. Ph.D. Dissertation.1990.
[128] Xiaozhong Geng, Gaochao Xu, Yuan Zhang. Dynamic load balancing schedulingmodel based on multi-core processor[C]. The5th International Conference on Frontierof Computer Science and Technology, FCST2010, p398-403,2010.
[129] S.K.Baruah. Feasibility Analysis of Preemptive Real-time Systems UponHeterogeneous Multiprocessor Platforms[C]. Proceedings of the25thIEEE IntemationalReal-time Systems Symposium[C]，2004:37-46.
[130]王群霞.基于集群的不确定因素下的动态负载平衡[D].浙江师范大学硕士论文.2007.
[131] Wenmin Miao, Dongni Li, Wei Zhang. A load-balancing dynamic scheduling algorithmunder machine failure conditions[C].2010International Conference on IntelligentComputation Technology and Automation, ICICTA2010, v1,144-147,2010.
[132] Beaumont O, Carter L, Ferrante J, Legrand A, Robert Y. Bandwidth-centric allocationof independent tasks on heterogeneous platforms[C]. Parallel and DistributedProcessing Symposium, Proceedings International, IPDPS2002,67-72.
[133] P. F. Dutot. Master-slave Tasking on Heterogeneous Processors.In International Paralleland Distributed Processing Symposium[C], page25b. IEEE Computer Society Press,April2003.
[134] Banino, C.; Beaumont, O.; Carter, L.; Ferrante, J.;etc.al.Scheduling strategies formaster-slave tasking on heterogeneous processor platforms[J]. Parallel and DistributedSystems, IEEE Transactions. April2004.15(4)319-330.
[135] P Dutot.Complexity of master-slave tasking on heterogeneoustrees[J]．European Journalon Operational Research．2005,164(3)：690-695.
[136] O H Ibarra, C E Kim．Heuristic algorithms for scheduling independent tasks onnonidentical processor[J]．Journal of the ACM.1977,24(2):280-289．
[137]蒋建春,汪同庆．异构多核处理器的任务调度算法[J]．计算机工程与应用，2009,45(33):52-56.
[138] Olivier Beaumont．Vinent Boudet，Yves Robert．A realistic model and efficientheuristic for scheduling with heterogeneous processor[C]．Proceedings of the16thInternational Parallel and Distributed Processing Symposium,2002,37-49．
[139] Braun TD, Siegel HJ, Beck N. A comparison of eleven static heuristics for mapping aclass of independent tasks onto heterogeneous distributed computing systems[J].Journal of Parallel and Distributed Computing,2001,61(6):810837.
[140] Haluk Topcuoglu, Salim Hariri, Min-You Wu. Task Scheduling Algorithms forHeterogeneous Processors[C]. Proceedings of the Heterogeneous Computing Workshop,HCW,1999:3-14.
[141] SETI at home, URL: http://setiathome.ssl.berkeley.edu.
[142] Cyril Banino. A Distributed Procedure for Bandwidth-Centric Scheduling ofIndependent-Task Applications[J]. Parallel and Distributed Processing Symposium,[C]2005. Proceedings.19th IEEE International,2005:48a-48a.
[143] L.Wei-Wei. Independent Tasks Scheduling on Tree-Based Grid Computing Platforms[j].Journal of Software,200617(11):2352-2361.
[144] Karmarkar N. A new polynomial-time algorithm for linear programming[J].Combinatorica,1984,4(4):373-395.
[145] Emanuele Goldoni, Giuseppe Rossi, Alberto Torelli. Assolo, a New Method forAvailable Bandwidth Estimation[C].2009Fourth International Conference on InternetMonitoring and Protection.
[146]张晓杰，孟庆春，曲卫芬．基于蚁群优化算法的服务网格的作业调度［Ｊ］．计算机工程，2006,32(8):216-218.
[147]王历.基于树形网络的云计算环境下的任务调度策略[D].《吉林大学硕士论文》2012.7.
[148] Casanova, H. Legrand, A.; Quinson, M. SimGrid: A Generic Framework forLarge-Scale Distributed Experiments. Computer Modeling and Simulation,2008.UKSIM2008. Tenth International Conference126-131.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |