异构多核嵌入式软件关键问题研究
|
摘要
如何充分利用异构多核处理器的异构特性,将单核的应用软件快速的移植到多核处理器上以及快速地开发基于多核处理器的应用程序是多核处理器应用中面临的主要问题。而解决这些问题的方法要求主要集中在多核软件等关键技术研究上,只有开发出与异构多核硬件相适应的操作系统及其应用软件,才能真正地发挥异构多核处理器的性能。
由于异构多核处理器中不同性质程序在不同内核的执行效率存在差异,且应用系统存在功耗、效率、实时性等要求,这就要求操作系统能够对任务进行有效的管理,如分配调度、通信、同步等,以实现多核处理器的最大化利用。而要实现这些功能必须针对异构多核处理器特点研究和设计相应的操作系统架构、调度算法、通信与同步机制等关键技术。传统的多处理器和分布式计算机与异构多核处理器在架构和通信机制上存在巨大差别,相应的分布式操作系统也不适用于异构多核处理器,特别是在嵌入式系统领域。
本课题针对嵌入式系统领域,通过研究异构多核处理器的结构特点,分别在操作系统架构、任务划分、异构核间的任务分配以及同构核间动态任务调度等几个关键问题方面进行了大量深入的研究,主要完成了以下工作:
1.研究了异构多核的操作系统架构
针对多处理器系统的分布式结构以及应用于同构多核系统的主从式结构操作系统不能解决异构多核处理器的实时调度和效率问题,本课题提出一种适用异构多核处理器的多主模式实时操作系统架构。这种架构将通信总线中的多主模式引入多核操作系统架构中,采用对称式结构及组件模式设计操作系统模型,使多核处理器中每个内核都可以作为主核实现对资源、任务的实时管理,提高系统性能,同时可以解决主从式操作系统存在的由于处理器核增多而带来的主内核不能满足系统性能要求存在的瓶颈问题。通过这种单一架构模型可以进行灵活配置适应不同结构及功能要求处理器内核,降低操作系统开发难度。
2.研究了异构多核处理器的任务划分问题
任务的调度与任务的属性、粒度、任务之间的关系等因素密不可分。异构多核的任务划分是多目标优化问题,怎样针对具体的任务执行环境进行任务分割,使任务在粒度大小、通信调度花费、并行化处理、负载均衡等方面得到一个有效的综合,从而通过调度获得系统的最大执行效率,是任务划分需要解决的关键问题。本课题从任务本身属性和调度两个方面针对异构多核处理器的任务划分中的重要影响因素进行分类分析,提出一种基于聚合性的微粒群分层任务划分方法,通过参数匹配,获得一个较好的划分结果,从而提高任务调度和执行的效率。
3.研究了异构多核处理器的任务静态调度问题
在异构多核处理器中,任务有最小最大完成时间、负载均衡、最低功耗等要求,异构环境下的任务分配和作业调度问题往往是局部目标和全局目标是相互制约,不能同时满足,任务静态调度被证明是一个NP-Hard的组合优化问题。本课题针对异构并行系统的作业调度和任务分配问题进行研究,提出一种基于Sufferage启发式算法和DPSO(Discrete Particle Swarm Optimization)算法的混合离散微粒群SDPSO (Sufferage Discrete Particle Swarm Optimization)独立任务分配算法,改进DPSO算法效率和搜索精度。由于实际的任务之间存在耦合性,针对独立任务设计的静态调度算法不能很好解决非独立任务的调度问题。因此,本课题在SDPSO算法的基础上,根据任务划分实际存在的耦合性,研究并提出一种基于耦合性的SDPSO静态任务调度改进算法。
4.研究了异构多核中同构核间的任务动态调度问题
在异构多核处理器中,有可能存在多个同构核,在这些同构核中的任务除了进行任务的静态分配以外,还存在运行过程中的动态调度问题。在动态调度中主要存在基于任务复制和基于表的动态调度算法,而基于任务复制的动态调度算法对存储空间要求较高不适合实时系统。本课题针对嵌入式系统并行同步任务的实时性要求在动态表的基础上提出一种基于任务划分的最小最大关键点执行时间MMKPT(Min-Max Key Point Time)算法,该算法根据同步任务的同步执行时间点和任务之间的耦合性对就绪任务和执行内核进行选择和调度,以满足嵌入式系统的实时性要求。
通过这些关键技术的研究工作及成果,可以为异构多核处理器的实时操作系统的研究与开发提供一些帮助和参考,以促进异构多核处理器的应用推广。
In the application of the heterogeneous multicore processor (HMP), how to make full use of the heterogeneous multi-core processor and how to quickly transfer and develop the application programs in multi-core processor are the most important issues. The solving methods of these problems focus on the researches of some key software techniques, such as multi-core operating system (OS), application programs, and so on.
Since different applications have different requirements for power, efficient, real-time, etc, OS is needed to manage tasks, such as scheduling, communication, synchronization, to utilize processor fully. So, the architecture of OS, the scheduling algorithm, the communication and synchronization mechanism, must be designed according to the characteristics of HMP. However, owing to the difference on architecture and communication mechanism, the traditional multiprocessors OS and distributed OS are not suitable to the HMP, especially in the embedded system application.
This thesis studies these key problems based on the research of the characteristics of HMP in embedded system area, including the OS architecture, the communication and synchronic mechanism, the task partitioning, the task static scheduling and the dynamic scheduling. The main contributions of the thesis are as follows:
1. OS architecture
Aim at the executing efficiency and real-time scheduling problems that can not be solved by the distributing structure and master-slave mode architecture OS of multi-processors and homogeneous multicore processor, a new multi-master mode OS architecture for HMP is proposed. In this architecture, because of the introduction of the multi-master mode of communication bus and the adoption of the symmetric structure and the modularization method in OS model design, each core could be as the master core in multi-core processor to manage tasks, resources, and so on. Meanwhile, this OS architecture can solve the bottleneck problem that the master-slave architecture can not do well because of the increasing slave number in single master OS. This model can be configured flexibly based on the requirements of application, and decrease the OS implement difficulty.
2. Task partition
In multi-core processor, task scheduling is strictly related with the task attribute, the task granularity, the relations between tasks and other factors. The task partition is a multi-goals optimization problem. The key issue of task partition is how to partition tasks based on different application to make system executing efficiently. Some factors, such as scheduling cost, granularity, coupling cost and load balancing, need to be taken into account. This paper firstly classify the tasks according to task attribute and system efficiency, including coupling cost, scheduling cost, and then presents one task partitioning algorithm based on cohesion and coupling of modules. This algorithm can achieve a good partitioning result, improve the task scheduling and executing efficiently through parameters matching.
3. Static task scheduling
In the HMP, tasks have the requirements of min-max complement time, load balance, lowest power cost, and so on. The global goals and the local targets are nomal mutually exclusive.The task allocation and scheduling is a multi-goals combinatorial optimization issue, and is proved a NP-hard problem. Through researching the task scheduling and assignation, this thesis puts forward a sufferage discrete particle swarm optimization (SDPSO) independent task static scheduling algorithm based on Sufferage and DPSO, which can improve the search efficiency and precision of DPSO.
In the practical application, there are coupling relations between tasks, and the independent task static scheduling algorithm can not settle well for the dependent tasks. So this paper modifies the SDPSO algorithm based on coupling attribute to make it suitable for the dependent tasks.
4. Dynamic task scheduling
Since there are a few homogeneous cores in HMP, dynamic scheduling is required among homogeneous cores except for static scheduling. The main algorithms are based on task duplication and list scheduling, and the task duplication algorithms is not suitable for embedded real-time system because of the requirement for large memory space. Therefore, this paper presents a min-max key point time (MMKPT) algorithm based on dynamic list scheduling algorithm, in which the ready task and kernel are selected according to the synchronization point executing time and the coupling relation among tasks to meet with the real-time performance requirement of the embedded system.
The research results of above key issues can provide some help and references for the HMP OS design and development, and advance the HMP to be applied more and more widely.
由于异构多核处理器中不同性质程序在不同内核的执行效率存在差异,且应用系统存在功耗、效率、实时性等要求,这就要求操作系统能够对任务进行有效的管理,如分配调度、通信、同步等,以实现多核处理器的最大化利用。而要实现这些功能必须针对异构多核处理器特点研究和设计相应的操作系统架构、调度算法、通信与同步机制等关键技术。传统的多处理器和分布式计算机与异构多核处理器在架构和通信机制上存在巨大差别,相应的分布式操作系统也不适用于异构多核处理器,特别是在嵌入式系统领域。
本课题针对嵌入式系统领域,通过研究异构多核处理器的结构特点,分别在操作系统架构、任务划分、异构核间的任务分配以及同构核间动态任务调度等几个关键问题方面进行了大量深入的研究,主要完成了以下工作:
1.研究了异构多核的操作系统架构
针对多处理器系统的分布式结构以及应用于同构多核系统的主从式结构操作系统不能解决异构多核处理器的实时调度和效率问题,本课题提出一种适用异构多核处理器的多主模式实时操作系统架构。这种架构将通信总线中的多主模式引入多核操作系统架构中,采用对称式结构及组件模式设计操作系统模型,使多核处理器中每个内核都可以作为主核实现对资源、任务的实时管理,提高系统性能,同时可以解决主从式操作系统存在的由于处理器核增多而带来的主内核不能满足系统性能要求存在的瓶颈问题。通过这种单一架构模型可以进行灵活配置适应不同结构及功能要求处理器内核,降低操作系统开发难度。
2.研究了异构多核处理器的任务划分问题
任务的调度与任务的属性、粒度、任务之间的关系等因素密不可分。异构多核的任务划分是多目标优化问题,怎样针对具体的任务执行环境进行任务分割,使任务在粒度大小、通信调度花费、并行化处理、负载均衡等方面得到一个有效的综合,从而通过调度获得系统的最大执行效率,是任务划分需要解决的关键问题。本课题从任务本身属性和调度两个方面针对异构多核处理器的任务划分中的重要影响因素进行分类分析,提出一种基于聚合性的微粒群分层任务划分方法,通过参数匹配,获得一个较好的划分结果,从而提高任务调度和执行的效率。
3.研究了异构多核处理器的任务静态调度问题
在异构多核处理器中,任务有最小最大完成时间、负载均衡、最低功耗等要求,异构环境下的任务分配和作业调度问题往往是局部目标和全局目标是相互制约,不能同时满足,任务静态调度被证明是一个NP-Hard的组合优化问题。本课题针对异构并行系统的作业调度和任务分配问题进行研究,提出一种基于Sufferage启发式算法和DPSO(Discrete Particle Swarm Optimization)算法的混合离散微粒群SDPSO (Sufferage Discrete Particle Swarm Optimization)独立任务分配算法,改进DPSO算法效率和搜索精度。由于实际的任务之间存在耦合性,针对独立任务设计的静态调度算法不能很好解决非独立任务的调度问题。因此,本课题在SDPSO算法的基础上,根据任务划分实际存在的耦合性,研究并提出一种基于耦合性的SDPSO静态任务调度改进算法。
4.研究了异构多核中同构核间的任务动态调度问题
在异构多核处理器中,有可能存在多个同构核,在这些同构核中的任务除了进行任务的静态分配以外,还存在运行过程中的动态调度问题。在动态调度中主要存在基于任务复制和基于表的动态调度算法,而基于任务复制的动态调度算法对存储空间要求较高不适合实时系统。本课题针对嵌入式系统并行同步任务的实时性要求在动态表的基础上提出一种基于任务划分的最小最大关键点执行时间MMKPT(Min-Max Key Point Time)算法,该算法根据同步任务的同步执行时间点和任务之间的耦合性对就绪任务和执行内核进行选择和调度,以满足嵌入式系统的实时性要求。
通过这些关键技术的研究工作及成果,可以为异构多核处理器的实时操作系统的研究与开发提供一些帮助和参考,以促进异构多核处理器的应用推广。
In the application of the heterogeneous multicore processor (HMP), how to make full use of the heterogeneous multi-core processor and how to quickly transfer and develop the application programs in multi-core processor are the most important issues. The solving methods of these problems focus on the researches of some key software techniques, such as multi-core operating system (OS), application programs, and so on.
Since different applications have different requirements for power, efficient, real-time, etc, OS is needed to manage tasks, such as scheduling, communication, synchronization, to utilize processor fully. So, the architecture of OS, the scheduling algorithm, the communication and synchronization mechanism, must be designed according to the characteristics of HMP. However, owing to the difference on architecture and communication mechanism, the traditional multiprocessors OS and distributed OS are not suitable to the HMP, especially in the embedded system application.
This thesis studies these key problems based on the research of the characteristics of HMP in embedded system area, including the OS architecture, the communication and synchronic mechanism, the task partitioning, the task static scheduling and the dynamic scheduling. The main contributions of the thesis are as follows:
1. OS architecture
Aim at the executing efficiency and real-time scheduling problems that can not be solved by the distributing structure and master-slave mode architecture OS of multi-processors and homogeneous multicore processor, a new multi-master mode OS architecture for HMP is proposed. In this architecture, because of the introduction of the multi-master mode of communication bus and the adoption of the symmetric structure and the modularization method in OS model design, each core could be as the master core in multi-core processor to manage tasks, resources, and so on. Meanwhile, this OS architecture can solve the bottleneck problem that the master-slave architecture can not do well because of the increasing slave number in single master OS. This model can be configured flexibly based on the requirements of application, and decrease the OS implement difficulty.
2. Task partition
In multi-core processor, task scheduling is strictly related with the task attribute, the task granularity, the relations between tasks and other factors. The task partition is a multi-goals optimization problem. The key issue of task partition is how to partition tasks based on different application to make system executing efficiently. Some factors, such as scheduling cost, granularity, coupling cost and load balancing, need to be taken into account. This paper firstly classify the tasks according to task attribute and system efficiency, including coupling cost, scheduling cost, and then presents one task partitioning algorithm based on cohesion and coupling of modules. This algorithm can achieve a good partitioning result, improve the task scheduling and executing efficiently through parameters matching.
3. Static task scheduling
In the HMP, tasks have the requirements of min-max complement time, load balance, lowest power cost, and so on. The global goals and the local targets are nomal mutually exclusive.The task allocation and scheduling is a multi-goals combinatorial optimization issue, and is proved a NP-hard problem. Through researching the task scheduling and assignation, this thesis puts forward a sufferage discrete particle swarm optimization (SDPSO) independent task static scheduling algorithm based on Sufferage and DPSO, which can improve the search efficiency and precision of DPSO.
In the practical application, there are coupling relations between tasks, and the independent task static scheduling algorithm can not settle well for the dependent tasks. So this paper modifies the SDPSO algorithm based on coupling attribute to make it suitable for the dependent tasks.
4. Dynamic task scheduling
Since there are a few homogeneous cores in HMP, dynamic scheduling is required among homogeneous cores except for static scheduling. The main algorithms are based on task duplication and list scheduling, and the task duplication algorithms is not suitable for embedded real-time system because of the requirement for large memory space. Therefore, this paper presents a min-max key point time (MMKPT) algorithm based on dynamic list scheduling algorithm, in which the ready task and kernel are selected according to the synchronization point executing time and the coupling relation among tasks to meet with the real-time performance requirement of the embedded system.
The research results of above key issues can provide some help and references for the HMP OS design and development, and advance the HMP to be applied more and more widely.
引文
[1] Zheng Li,从多核到众核处理器[EB/OL]. http://www.kunli.info/2010/12/21/from-multicore- to-manycore/, 2010,12, 21.
[2]计算所微处理器中心,多核CPU和众核CPU之IBM Cell处理器[EB/OL]. http://www. bjkp. gov.cn/bjkpzc/kjqy/it/cpu/247110.shtml,2009,7,15
[3]黄国睿,张平,魏广博.多核处理器的关键技术及其发展趋势[J].计算机工程与设计, 2009,10(30):2414-2418
[4]竹居智久,处理器向异构多核架构发展[J].电子设计应用,2008,01:16.
[5] Intel. Intel@CoreTM2 Duo processor [EB/OL]. http://www.intel.com/products/processor_number/eng/chart/core2duo.htm.
[6] Kahle, J.A., et a1. Introduction to the cell multiprocessor [J]. IBM Journal of Research and Development. 2005, 49 (4-5):589-604.
[7]邓让钰,陈海燕等,一种异构多核处理器的并行流存储结构[J].电子学报, 2009, 37(2):312-317.
[8] Jason Schlessman, Mark Lodato, Burak Ozer, Wayne Wolf. Heterogeneous MPSoC Architectures for Embedded Computer Vision[C]. 2007 IEEE International Conference on Multimedia and Expo:1870–1873.
[9]迎九,多核/虚拟化/多操作系统的软件趋势[J].电子产品世界, 2010,17(1):58-60.
[10] Xavier Guérin, Frédéric Pétrot, A System Framework for the Design of Embedded Software Targeting Heterogeneous Multi-core SoCs[C]. 2009 20th IEEE International Conference on Application-specific Systems, Architectures and Processors, 2009:153-160.
[11] Peter Kollig,Colin Osborne, Tomas Henriksson. Heterogeneous Multi-Core Platform for Consumer Multimedia Applications. Design[C]. Automation & Test in Europe Conference & Exhibition:1254-1259, 2009.
[12]戴鸿君,基于异构多核体系与组件化软件的嵌入式系统研究[D].浙江大学,2007.
[13]蒋汉平,面向多核网络处理器软件框架的研究与实现[D].武汉理工大学, 2008.
[14]陈云川,面向多核处理器的嵌入式操作系统研究——基于Blackfin561与μCLinux[D].电子科技大学, 2009.
[15]顾宝刚,基于VxWorks的异构多核处理器软件系统的研究与设计[D].国防科学技术大学, 2008.
[16]谢铖,多内核构件化嵌入式操作系统的研究[D].浙江大学,2006.
[17]张荫芾,基于多核处理器架构的嵌入式微内核操作系统的研究与设计[D].上海交通大学,2009.
[18]艾定军,徐家祥,蒋祥刚等.实时嵌入式多处理器操作系统实现框架[J].计算机工程,2003,29(10):89-91
[19] Steve Muir, Jonathan Smith, AsyMOS-an Asymmetric Multiprocessor Operating System[J]. In: Proceedings of Open Architectures and Network Programming, 1998:25-34.
[20] Minyeol Seo, Ha Seok Kim, Ji Chan Maeng, Jimin Kim,and Minsoo Ryu: An Effective Design of Master-Slave Operating System Architecture for Multiprocessor Embedded Systems[C].In: Proceedings of Lecture Notes in Computer Science,.12th Asia-Pacific Conference, Seoul, Korea (2007):114-125.
[21] Jing Chen, Jian-Hong Liu, Developing Embedded Kernel for System-On-a-Chip Platform of Heterogeneous Multiprocessor Architecture[C]. 12th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA'06), 2006:246-250.
[22]风河推出新版VxWorks,助设备商发挥多核能力[J].中国新通信,2009,5: 95-95.
[23] Nathan Fisher, James H. Anderson, Sanjoy K. Baruah. Task partitioning upon memory-constrained multiprocessors[C].11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2005), Hong Kong, China 2005,8:416-421.
[24] Sathish Gopalakrishnan, Marco Caccamo. Task partitioning with replication upon heterogeneous multiprocessor systems[C]. RTAS '06 Proceedings of the 12th IEEE Real-Time and Embedded Technology and Applications Symposium, 2006,4:199-207.
[25] Sanjoy K. Baruah, Partitioning real-time tasks among heterogeneous multiprocessors[C]. Proceedings of the 2004 International Conference on Parallel Processing (ICPP’04):467-474.
[26] S. Arash Ostadzadeh, Roel J. Meeuws, Kamana Sigdel, Koen Bertels. A Multipurpose Clustering Algorithm for Task Partitioning in Multicore Reconfigurable Systems[C]. International Conference on Complex, Intelligent and Software Intensive Systems - CISIS ,2009: 663-668.
[27]郑凯,对数据在异构多核处理器模拟器中进行任务划分的研究[D].上海交通大学, 2008.
[28] Xie Yuan,Hung Wei-lun.Temperaturaware task allocation and scheduling for embedded multiprocessor systems-on-chip (MPSoC) design[J].Journal of VLSI Signal Processing,2006,5(3):177 -189.
[29]李仁发,刘彦,徐成.多处理器片上系统任务调度研究进展评述[J].计算机研究与发展, 2008,45(9):1620-1629.
[30]董珍,异构多核处理器的任务调度分配问题及算法研究[D].哈尔滨工程大学, 2010.
[31]徐立超,异构多核处理器的任务分配及能耗研究[D].湖南大学, 2010.
[32]刘彦,异构多核片上系统的任务调度及应用研究[D].湖南大学,2009.
[33]潘东,多核环境任务分配问题复杂性及求解模型研究[D].大连理工大学, 2009.
[34]兰舟,分布式系统中的调度算法研究[D].电子科技大学, 2008.
[35]吴彤,弱硬实时调度关键技术研究[D].国防科学技术大学,2008.
[36]张晓燕,P2P环境下多目标任务调度策略研究[D].大连理工大学, 2008.
[37] Euiseong Seo, Jinkyu Jeong, Seonyeong Park, and Joonwon Lee.Energy Efficient Scheduling of Real-Time Tasks on Multicore Processors[J]. IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2008, 19(11):1540-1552.
[38] Braun T D, Siegel H J, Beck N,et a1.A Comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing Systems[J]. Journal of Parallel and Distributed Computing, 2001, 6l(6):810-837.
[39] Izakian, H.; Abraham, A.; Sná?el, V. Comparison of heuristics for scheduling independent tasks on heterogeneous distributed environments[C]. In Proceedings of the IEEE International Workshop on HPC and Grid Applications, Sanya, P.R. China, April 24-26, 2009:8-12.
[40] Salman A,Ahmad I.AI-Madam S.Particle Swarm Optimization for Task Assignment Problem[J].Microprocessors and Microsystems,2002, 26(8):363- 37l.
[41] M. B. Abdelhalim.Task assignment for Heterogeneous Multiprocessors using Re-Excited Particle Swarm Optimization[C]. 2008 International Conference on Computer and Electrical Engineering:23-27.
[42] MAHESWARAN M, AU S, SIEGEL H J, et a1.A comparison of dynamic strategies for mapping a class of independent tasks onto heterogeneous computing systems[R]. School of Electrical and Computer Engineering,Purdue University, in preparation, 1999.
[43]宾雪莲,杨玉海,金士尧.一种基于分组与适当选择策略的实时多处理器系统的动态调度算法[J].计算机学报, 2006, 29(1):81-91.
[44]刘俊海,多核系统内存管理算法的设计与实现[D].天津大学, 2008.
[45]史成伟,多核系统中的内存管理系统优化研究[D].电子科技大学, 2009.
[46] Maurice Herlihy, Nir Shavit著.金海,胡侃译.多处理器编程的艺术[M].北京:机械工业出版社, 2009,8:49-82,141-145.
[47] Bodhisattwa Mukherjee, Karsten Schwan, Prabha Gopinath. A Survey of Multiprocessor Operating System Kernels[R], Technical Report in GIT–CC–92- /05, November,1993:4-11.
[48] Goble, G.H., Marsh, M.H., A Dual Processor VAX 11/780[C]. In: Proceedings of the 9th Annual Symposium on Computer Architecture: 291–298 (1982).
[49] Kagstrom, S., Lundberg, L., Grahn, H.: A Novel Method for Adding Multiprocessor Support to a Large and Complex Uniprocessor Kernel[C]. In: Proceedings of 18th InternationalParallel and Distributed Processing Symposium, 2004:60-70.
[50]章承科,基于多核处理器的实时操作系统的扩展[D].硕士学位论文,电子科技大学, 2006.
[51] Wu, M. and X. Sun. Memory Conscious Task Partition and Scheduling in Grid Environments[C]. Proceedings in the 5th IEEE/ACM International Workshop on Grid Computing. 2004: IEEE Computer Society.
[52] Lastovetsky, A. and R. Reddy, Data partitioning for multiprocessors with memory heterogeneity and memory constraints[J]. Sci. Program. 2005,13(2):93-112.
[53] Seungyong Oh, Jungsoo Kim, Seonpil Kim , Chong-Min Kyung.Task Partitioning Algorithm for Intra-Task Dynamic Voltage Scaling[R]. International Symposium on Circuits and Systems (ISCAS 2008):1228-1231.
[54]姚放吾,卢昭材.基于权重可变免疫算法的动态可重构任务划分[J].计算机技术与发展,2009, l9(7):52-55.
[55] Jian-Jia Chen, Lothar Thiele. Energy-Efficient Task Partition for Periodic Real-Time Tasks on Platforms with Dual Processing Elements[C]. 14th IEEE International Conference on Parallel and Distributed Systems(ICPADS '08):162-168.
[56] G. Wang, W. Gong, R. Kastner. Application Partitioning on Programmable Platforms Using the Ant Colony Optimization[J]. Journal of Embedded Computing, 2(1):119–136, 2006.
[57] T. Wiangtong, P. Y. K. Cheung, and W. Luk. Comparing Three Heuristic Search Methods for Functional Partitioning in HardwareSoftware Codesign[J]. Design Automation for Embedded Systems, 6(4):425–449, 2002.
[58] T. Wiangtong, P. Y. K. Cheung, and W. Luk. Tabu Search with Intensification Strategy for Functional Partitioning in Hardware-Software Codesign[C]. In Proceedings of the 10th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, pages 297–298, 2002.
[59] B. B. AGARWAL,S. P. TAYAL,M. GUPTA. Software engineering & testing an introduction[M]. America:Jones and Bartlett Publishers, 2008.
[60] M. Pinedo, ``Scheduling: Theory, Algorithms, and Systems,'' Prentice_Hall, Englewood Cliffs, NJ, 1995.
[61] T. Braun, H. Siegel, N. Beck, L. Boloni, M. Maheswaran, A. Reuther, J. Robertson, M. Theys, B.Yao, D. Hensgen, and R. Freund. A comparison study of static mapping heuristics for a class of meta-tasks on heterogeneous computing systems[C]. In 8th IEEE Heterogeneous Computing Workshop (HCW’99), pages 15–29, Apr. 1999.
[62] J U Ilman. N P-Complete Scheduling Problems[J]. Journal of Compute r and System Sciences,l975, (10):384-393.
[63] C. H. Papadimitriou,M Yannakakis. Scheduling Interval-ordered Tasks [J]. SIAM Journal on Computing, 1979, 8 (3 ):405-409.
[64] D. Fernandez-Baca, Allocating modules to processors in a distributed system[J]. IEEE Transactions on Software Engineering. 1989,15(11):1427-1436.
[65]何炎祥,吴思等.一种改进的启发式任务分配算法[J].计算机研究与发. 1998, 35(3):219-223.
[66]邱卫东,陈燕等.一种实时异构嵌入式系统的任务调度算法[J].软件学报,2004,15(4): 504-511.
[67] Carpenter, J., Funk, S., Holman, P., Srinivasan, A., Anderson, J., Baruah, S.: A Categorization of Real-Time Multiprocessor Scheduling Problems and Algorithms[Z]. In: Leung, J.Y.-T. (ed.) Handbook of Scheduling: Algorithms, Models, and Performance Analysis, Chapman Hall/CRC Press, Boca Raton, USA (2004).
[68]罗宏伟,吴斌等.快速启发式多约束优化路径算法研究,自动化与仪表[J].2008.9:5-8.
[69] R. Armstrong, D. Hensgen, and T. Kidd. The relative performance of various mapping algorithms is independent of sizable variances in run-time predictions[C]. In 7th IEEE Heterogeneous Computing Workshop (HCW’98), pages 79-87, Mar.1998.
[70] R. Freund, M. Gherrity, S. Ambrosius, M. Campbell, M. Halderman, D. Hensgen, E. Keith, T. Kidd, M. Kussow, J. Lima, F. Mirabile, L. Moore, B. Rust, and H. Siegel. Scheduling resources in multi-user, heterogeneous, computing environments with SmartNet[C]. In 7th IEEE Heterogeneous Computing Workshop (HCW’98), pages 184–199, Mar. 1998.
[71] R. F. Freund and H. J. Siegel. Heterogeneous processing[J]. IEEE Computer, 26(6):13–17, June 1993.
[72] O. Ibarra and C. Kim. Heuristic algorithms for scheduling independent tasks on nonidentical processors[J]. Journal of the ACM, 77(2):280–289, Apr. 1977.
[73] Thomas S , Holger H H.MAX-MIN ant system [J]. Future Generation Computer Systems(S0167-739X),2000,16(8):889-914.
[74] Stiitzle T,HoosH.MAX-M IN an t system an d loc al search fur the traveling salesman problem [C].In Proceedings of the 1997 IEEE International Conference on Evolutionary Computation.New York: IEEE Press,1997:309-314.
[75] Temlyakov V N.Greedy algorithm with regard to multi-variate systems with special structure[J].Constr. Approx, 2000,16:399-425.
[76] Kavitha S. Golconda, Füsun ?zgüner, Atakan Do?an, A Comparison of Static QoS-Based Scheduling Heuristics for a Meta-Task with Multiple QoS Dimensions in HeterogeneousComputing[C]. In Proceedings of the 18th International Parallel and Distributed Processing Symposium (IPDPS'04) Santa Fe, New Mexico 2004:106.
[77] ZHANG Jinquan, NI Lina, JIANG Changjun. A heuristic scheduling strategy for independent tasks on grid[C].In: Proceedings of the 8th International Conference on High-Performance Computing in Asia-Pacific Region. Los Alamitos, Cal. , USA: IEEE Computer Society, 2005 : 588-593.
[78] Ding, Ding; Luo, Siwei; Gao, Zhan.A Dual Heuristic Scheduling Strategy Based on Task Partition in Grid Environments[C]. In: Proceedings of International Joint Conference on Computational Sciences and Optimization, 2009:63-67.
[79] H. Singh and A. Youssef. Mapping and scheduling heterogeneous task graphs using genetic algorithms[C]. In 5th IEEE Heterogeneous Computing Workshop (HCW’96), pages 86-97, Apr. 1996.
[80] L. Wang, H. J. Siegel, V. P. Roychowdhury, and A. A. Maciejewski.Task matching and scheduling in heterogeneous computing environments using a genetic-algorithm-based approach[J]. Journal of Parallel and Distributed Computing, 47(1):1-15, Nov. 1997.
[81]钟求喜,谢涛,陈火旺.基于遗传算法的任务调度与分配[J].计算机研究与发展,2000,37(10):1197-1203.
[82] Back, T.,Evolutionary Algorithms in Theory and Practice[M]. Oxford university Press, New York, 1995
[83]纪树新等,遗传算法在车间调度中的应用[J].系统工程理论与实践,1998,18(5): 34-39.
[84]刘勇,康立山等,非数值并行计算(第二册)——遗传算法[M],北京:科学出版社,1995.
[85]王凌,郑大钟,基于遗传算法的Job Shop调度研究进展[J],控制与决策,2001,11(16): 641-645.
[86]王凌编著,车间调度及其遗传算法[M],北京:清华大学出版社,2003.5.
[87] Edwin S H,Hou Nirwan An sari.Genetic algorithm for multiprocessor scheduling [J].IEEE Trans on Parallel and Distributed Systems(S1045-9219), 1994,5(2):113-120.
[88]马学彬,温涛等.一种基于遗传算法的网格任务调度算法[J].东北大学学报(自然科学版).2007,28(7):973-977.
[89]钟求喜,谢涛,陈火旺.基于遗传算法的任务分配与调度[J].计算机研究与发展,2000,37(10):1197-1203.
[90] M. Coli and P. Palazzari. Real time pipelined system design through simulated annealing[J]. Journal of Systems Architecture, 42(6-7):465–475, Dec. 1996.
[91] S. Kirkpatrick, J. C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science[J]. 220(4598):671–680, May 1983.
[92]刘勇,康立山等,非数值并行计算(第一册)——模拟退火算法[M],北京:科学出版社,1994
[93] Hironori Kasahara.Seinosuke Narita Practical multiprocessor scheduling algorithms fur efficient parallel processing[J].IEEE Trans on Computers(S0018-9340),1984, 33(11) :1023-1029.
[94] Armastrong R,Hensgen D,Kidd T. The relative performance of various mapping algorithms is independent of sizable variances in run-time predictions [C]In: 7th IEEE Heterogeneous Computing Workshop.Washington D.C: IEEE Computer Society. 1998: 79-87.
[95] Freund RF, Gherrity M, Ambrosius S, et a1. Scheduling resources in multi-user, heterogeneous,computing environments with Smart Net[C] In:7th IEEE Heterogeneous Computing Workshop.Washington D.C:IEEE Computer Society.1998:184-199.
[96] Xu Zhihong,Hou Xiangdan ,Sun Jizhou.Ant Algorithm- based Task Scheduling in Grid Computing[C]. IEEE Canadian Conference on Electrical and Computer Engineering. Washington D.C: IEEE Computer Society,2003:1107-1110.
[97]段海滨.蚁群算法原理及其应用[M].北京:科学出版社, 2005.
[98]汪镭,吴启迪.智能蚁群算法及应用[M].上海:上海科学技术出版社, 2004.
[99] Dorigo M, Gambardella LM. Ant Colonied for the Traveling Salesman Problem [J].Biosystems(S0303-2647),1997,43(2):73-82.
[100] Stiitzie T,Dorigo M.ACO Algorithms for the Quadratic Assignment Problem [C]. New Methods in Optimization.London:McGraw-Hill,1999:3-50.
[101] Colorni A,Dorigo M.Ant System for Job-shop Scheduling [J].Belgian Journal of operations Research,Statistics and Computer Science(S0770-0512), 1994, 34(1):39-53.
[102] Schoonderwoerd R , Hollan d O, Bruten J, et a1. Ant-based Load Balancing in Telecommunications Networks [J].Adaptive Behavior (S1059-7123),1996,5(2):169-207.
[103] Lian g Yc.Smi th Ae.An Ant System Approach to Redundancy Allocation[C].In: Proceedings of the 1999 Congress on Evolutionary Computation,Piscataway.New York:IEEE Press,1999:1478-1484.
[104] Clerc M.Discrete Particle Swarm Optimization , Illustrated by Traveling Salesman Problem[M ].Berlin:Springer-Verlag,2004.
[105]冯斌,孙俊.一种多处理机任务分配的启发式算法[J].计算机工程,2004,30(14):63-65.
[106] Kennedy J,Eberhart R C.Particle Swarm Optimization [C].In: Proceedings of the IEEE International Conference on Neural Networks.Perth,Australia:[s. n.],1995:1942-1948.
[107] Kennedy J,Eberhart R C A Discrete Binary Version of the Particle Swarm Algorithm[C]. In: Proceedings of the World Multi Conference on Systems, Cybernetics and Informatics. Piscataway, Nagoya,Japan:IEEE Service Center,1997:4104-4109.
[108]高尚,杨静宇.多处理机调度问题的粒子群优化算法[J].计算机工程与应用,2005,41(27):72-73.
[109]王凌.智能优化算法及其应用[M].北京:清华大学出版社,200l.
[110]王凌,刘波著.微粒群优化与调度算法[M].北京:清华大学出版社,2008.
[111] Min-You Wu, Wei Shu, Zhang, H. Segmented Min-Min: A Static Mapping Algorithm for Meta-tasks on Heterogeneous Computing Systems[C]. Proceedings of the 9th Heterogeneous Computing Workshop(HCW 2000):375-385.
[112] K.Rameshkumar, R.K. Suresh, and K.M.Mohanasundaram: Discrete Particle Swarm Optimization (DPSO) Algorithm for Permutation Flowshop Scheduling to Minimize Makspan[C]. In: Proc. ICNC 2005, LNCS 3612, (2005):572-581.
[113]钟一文,杨建刚.独立任务分配问题的离散粒子群优化算法[J].模式识别与人工智能,2006,19(3): 399-405.
[114]陈养平,王来雄,黄士坦.基于粒子群优化的多处理器任务调度算法[J].吉林大学学报(信息科学版), 2007, 25(3): 277-285.
[115] Peng-Yeng YinT, Shiuh-Sheng Yu, Pei-Pei Wang, Yi-Te Wang.A hybrid particle swarm optimization algorithm for optimal task assignment in distributed systems[J]. Computer Standards & Interfaces. 2006,28(4): 441-450.
[116] Tasgetiren MF, Liang YC, Sevkli M, Gencyilmaz G. A particle swarm optimization algorithm for makespan and total Flowtime minimization in the permutation flowshop sequencing problem[J]. European Journal of Operational Research. 2007,177(26):1930-1947.
[117] H. Chen and A. M. K. Cheng, Applying Ant Colony Optimization to the Partitioned Scheduling Problem for Heterogeneous Multiprocessors[J]. ACM SIGBED Review, 2005,2(2):11-14.
[118] Liang-Teh Lee, Hung-Yuan Chang, Kang-Yuan Liu, etc. A Dynamic Scheduling Algorithm in Heterogeneous Computing Environments[C]. International Symposium on Communications and Information Technologies, 2006: 313-318.
[119]王堃,乔颖等.实时异构系统的动态调度算法研究[J].计算机研究与发展, 2002,39(6):725-730.
[120]杨玉海,宾雪莲等.异构实时多处理器系统的动态调度算法研究[J].小型微型计算机系统, 2008, 29(1):130-134.
[121] Zhang Jie, Yang Fumin, Tu Gang. A Dynamic Scheduling Model for Real-Time Tasks in Reliable System[C]. In Proceedings of the 2009 International Conference on Networks Security, Wireless Communications and Trusted Computing,2009:185-188.
[122] A novel dynamic allocation and scheduling scheme with CPNA and FCF algorithms indistributed real-time systems[C]. Proceedings of the 11th International Conference on Parallel and Distributed Systems(ICPADS '05):550-556.
[123]丁丁,罗四维,高瞻.一种基于任务划分的启发式网格调度策略[J].北京交通大学学报,2007,11(5):72-76.
[124]周双娥,袁由光等.基于任务复制的处理器预分配算法[J].计算机学报,2004,27(2):216-222.
[125]姚文胜,薛广涛等.基于任务复制的进化调度算法[J].上海交通大学学报, 2004,36(5):755-762.
[126]林剑柠,吴慧中,陈学勤.基于任务复制的网格任务调度算法[J].计算机科学, 2006,33 (6): 89-105.
[127] Wang Q, Cheng K. H, List scheduling and parallel tasks [J]. Information Processing Letters, 1991, 37(5):78-87.
[128] Darbha S., Agrawal D. P. . Optimal scheduling algorithm for distributed-memory machines[J].IEEE Transactions on Parallel and Distributed Systems,1998, 9(1):87-95.
[129] Park Chan-Ik, Choe Tee-Young. An optimal scheduling algorithm based on task duplication[J].IEEE Transactions on Computers, 2002,51(4):444- 448.
[130] Gerold J?ger, An Efficient Algorithm for Graph Bisection of Triangularizations [J]. Applied Mathematical Sciences, 2007,1(25):1203-1215.
[2]计算所微处理器中心,多核CPU和众核CPU之IBM Cell处理器[EB/OL]. http://www. bjkp. gov.cn/bjkpzc/kjqy/it/cpu/247110.shtml,2009,7,15
[3]黄国睿,张平,魏广博.多核处理器的关键技术及其发展趋势[J].计算机工程与设计, 2009,10(30):2414-2418
[4]竹居智久,处理器向异构多核架构发展[J].电子设计应用,2008,01:16.
[5] Intel. Intel@CoreTM2 Duo processor [EB/OL]. http://www.intel.com/products/processor_number/eng/chart/core2duo.htm.
[6] Kahle, J.A., et a1. Introduction to the cell multiprocessor [J]. IBM Journal of Research and Development. 2005, 49 (4-5):589-604.
[7]邓让钰,陈海燕等,一种异构多核处理器的并行流存储结构[J].电子学报, 2009, 37(2):312-317.
[8] Jason Schlessman, Mark Lodato, Burak Ozer, Wayne Wolf. Heterogeneous MPSoC Architectures for Embedded Computer Vision[C]. 2007 IEEE International Conference on Multimedia and Expo:1870–1873.
[9]迎九,多核/虚拟化/多操作系统的软件趋势[J].电子产品世界, 2010,17(1):58-60.
[10] Xavier Guérin, Frédéric Pétrot, A System Framework for the Design of Embedded Software Targeting Heterogeneous Multi-core SoCs[C]. 2009 20th IEEE International Conference on Application-specific Systems, Architectures and Processors, 2009:153-160.
[11] Peter Kollig,Colin Osborne, Tomas Henriksson. Heterogeneous Multi-Core Platform for Consumer Multimedia Applications. Design[C]. Automation & Test in Europe Conference & Exhibition:1254-1259, 2009.
[12]戴鸿君,基于异构多核体系与组件化软件的嵌入式系统研究[D].浙江大学,2007.
[13]蒋汉平,面向多核网络处理器软件框架的研究与实现[D].武汉理工大学, 2008.
[14]陈云川,面向多核处理器的嵌入式操作系统研究——基于Blackfin561与μCLinux[D].电子科技大学, 2009.
[15]顾宝刚,基于VxWorks的异构多核处理器软件系统的研究与设计[D].国防科学技术大学, 2008.
[16]谢铖,多内核构件化嵌入式操作系统的研究[D].浙江大学,2006.
[17]张荫芾,基于多核处理器架构的嵌入式微内核操作系统的研究与设计[D].上海交通大学,2009.
[18]艾定军,徐家祥,蒋祥刚等.实时嵌入式多处理器操作系统实现框架[J].计算机工程,2003,29(10):89-91
[19] Steve Muir, Jonathan Smith, AsyMOS-an Asymmetric Multiprocessor Operating System[J]. In: Proceedings of Open Architectures and Network Programming, 1998:25-34.
[20] Minyeol Seo, Ha Seok Kim, Ji Chan Maeng, Jimin Kim,and Minsoo Ryu: An Effective Design of Master-Slave Operating System Architecture for Multiprocessor Embedded Systems[C].In: Proceedings of Lecture Notes in Computer Science,.12th Asia-Pacific Conference, Seoul, Korea (2007):114-125.
[21] Jing Chen, Jian-Hong Liu, Developing Embedded Kernel for System-On-a-Chip Platform of Heterogeneous Multiprocessor Architecture[C]. 12th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA'06), 2006:246-250.
[22]风河推出新版VxWorks,助设备商发挥多核能力[J].中国新通信,2009,5: 95-95.
[23] Nathan Fisher, James H. Anderson, Sanjoy K. Baruah. Task partitioning upon memory-constrained multiprocessors[C].11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2005), Hong Kong, China 2005,8:416-421.
[24] Sathish Gopalakrishnan, Marco Caccamo. Task partitioning with replication upon heterogeneous multiprocessor systems[C]. RTAS '06 Proceedings of the 12th IEEE Real-Time and Embedded Technology and Applications Symposium, 2006,4:199-207.
[25] Sanjoy K. Baruah, Partitioning real-time tasks among heterogeneous multiprocessors[C]. Proceedings of the 2004 International Conference on Parallel Processing (ICPP’04):467-474.
[26] S. Arash Ostadzadeh, Roel J. Meeuws, Kamana Sigdel, Koen Bertels. A Multipurpose Clustering Algorithm for Task Partitioning in Multicore Reconfigurable Systems[C]. International Conference on Complex, Intelligent and Software Intensive Systems - CISIS ,2009: 663-668.
[27]郑凯,对数据在异构多核处理器模拟器中进行任务划分的研究[D].上海交通大学, 2008.
[28] Xie Yuan,Hung Wei-lun.Temperaturaware task allocation and scheduling for embedded multiprocessor systems-on-chip (MPSoC) design[J].Journal of VLSI Signal Processing,2006,5(3):177 -189.
[29]李仁发,刘彦,徐成.多处理器片上系统任务调度研究进展评述[J].计算机研究与发展, 2008,45(9):1620-1629.
[30]董珍,异构多核处理器的任务调度分配问题及算法研究[D].哈尔滨工程大学, 2010.
[31]徐立超,异构多核处理器的任务分配及能耗研究[D].湖南大学, 2010.
[32]刘彦,异构多核片上系统的任务调度及应用研究[D].湖南大学,2009.
[33]潘东,多核环境任务分配问题复杂性及求解模型研究[D].大连理工大学, 2009.
[34]兰舟,分布式系统中的调度算法研究[D].电子科技大学, 2008.
[35]吴彤,弱硬实时调度关键技术研究[D].国防科学技术大学,2008.
[36]张晓燕,P2P环境下多目标任务调度策略研究[D].大连理工大学, 2008.
[37] Euiseong Seo, Jinkyu Jeong, Seonyeong Park, and Joonwon Lee.Energy Efficient Scheduling of Real-Time Tasks on Multicore Processors[J]. IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2008, 19(11):1540-1552.
[38] Braun T D, Siegel H J, Beck N,et a1.A Comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing Systems[J]. Journal of Parallel and Distributed Computing, 2001, 6l(6):810-837.
[39] Izakian, H.; Abraham, A.; Sná?el, V. Comparison of heuristics for scheduling independent tasks on heterogeneous distributed environments[C]. In Proceedings of the IEEE International Workshop on HPC and Grid Applications, Sanya, P.R. China, April 24-26, 2009:8-12.
[40] Salman A,Ahmad I.AI-Madam S.Particle Swarm Optimization for Task Assignment Problem[J].Microprocessors and Microsystems,2002, 26(8):363- 37l.
[41] M. B. Abdelhalim.Task assignment for Heterogeneous Multiprocessors using Re-Excited Particle Swarm Optimization[C]. 2008 International Conference on Computer and Electrical Engineering:23-27.
[42] MAHESWARAN M, AU S, SIEGEL H J, et a1.A comparison of dynamic strategies for mapping a class of independent tasks onto heterogeneous computing systems[R]. School of Electrical and Computer Engineering,Purdue University, in preparation, 1999.
[43]宾雪莲,杨玉海,金士尧.一种基于分组与适当选择策略的实时多处理器系统的动态调度算法[J].计算机学报, 2006, 29(1):81-91.
[44]刘俊海,多核系统内存管理算法的设计与实现[D].天津大学, 2008.
[45]史成伟,多核系统中的内存管理系统优化研究[D].电子科技大学, 2009.
[46] Maurice Herlihy, Nir Shavit著.金海,胡侃译.多处理器编程的艺术[M].北京:机械工业出版社, 2009,8:49-82,141-145.
[47] Bodhisattwa Mukherjee, Karsten Schwan, Prabha Gopinath. A Survey of Multiprocessor Operating System Kernels[R], Technical Report in GIT–CC–92- /05, November,1993:4-11.
[48] Goble, G.H., Marsh, M.H., A Dual Processor VAX 11/780[C]. In: Proceedings of the 9th Annual Symposium on Computer Architecture: 291–298 (1982).
[49] Kagstrom, S., Lundberg, L., Grahn, H.: A Novel Method for Adding Multiprocessor Support to a Large and Complex Uniprocessor Kernel[C]. In: Proceedings of 18th InternationalParallel and Distributed Processing Symposium, 2004:60-70.
[50]章承科,基于多核处理器的实时操作系统的扩展[D].硕士学位论文,电子科技大学, 2006.
[51] Wu, M. and X. Sun. Memory Conscious Task Partition and Scheduling in Grid Environments[C]. Proceedings in the 5th IEEE/ACM International Workshop on Grid Computing. 2004: IEEE Computer Society.
[52] Lastovetsky, A. and R. Reddy, Data partitioning for multiprocessors with memory heterogeneity and memory constraints[J]. Sci. Program. 2005,13(2):93-112.
[53] Seungyong Oh, Jungsoo Kim, Seonpil Kim , Chong-Min Kyung.Task Partitioning Algorithm for Intra-Task Dynamic Voltage Scaling[R]. International Symposium on Circuits and Systems (ISCAS 2008):1228-1231.
[54]姚放吾,卢昭材.基于权重可变免疫算法的动态可重构任务划分[J].计算机技术与发展,2009, l9(7):52-55.
[55] Jian-Jia Chen, Lothar Thiele. Energy-Efficient Task Partition for Periodic Real-Time Tasks on Platforms with Dual Processing Elements[C]. 14th IEEE International Conference on Parallel and Distributed Systems(ICPADS '08):162-168.
[56] G. Wang, W. Gong, R. Kastner. Application Partitioning on Programmable Platforms Using the Ant Colony Optimization[J]. Journal of Embedded Computing, 2(1):119–136, 2006.
[57] T. Wiangtong, P. Y. K. Cheung, and W. Luk. Comparing Three Heuristic Search Methods for Functional Partitioning in HardwareSoftware Codesign[J]. Design Automation for Embedded Systems, 6(4):425–449, 2002.
[58] T. Wiangtong, P. Y. K. Cheung, and W. Luk. Tabu Search with Intensification Strategy for Functional Partitioning in Hardware-Software Codesign[C]. In Proceedings of the 10th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, pages 297–298, 2002.
[59] B. B. AGARWAL,S. P. TAYAL,M. GUPTA. Software engineering & testing an introduction[M]. America:Jones and Bartlett Publishers, 2008.
[60] M. Pinedo, ``Scheduling: Theory, Algorithms, and Systems,'' Prentice_Hall, Englewood Cliffs, NJ, 1995.
[61] T. Braun, H. Siegel, N. Beck, L. Boloni, M. Maheswaran, A. Reuther, J. Robertson, M. Theys, B.Yao, D. Hensgen, and R. Freund. A comparison study of static mapping heuristics for a class of meta-tasks on heterogeneous computing systems[C]. In 8th IEEE Heterogeneous Computing Workshop (HCW’99), pages 15–29, Apr. 1999.
[62] J U Ilman. N P-Complete Scheduling Problems[J]. Journal of Compute r and System Sciences,l975, (10):384-393.
[63] C. H. Papadimitriou,M Yannakakis. Scheduling Interval-ordered Tasks [J]. SIAM Journal on Computing, 1979, 8 (3 ):405-409.
[64] D. Fernandez-Baca, Allocating modules to processors in a distributed system[J]. IEEE Transactions on Software Engineering. 1989,15(11):1427-1436.
[65]何炎祥,吴思等.一种改进的启发式任务分配算法[J].计算机研究与发. 1998, 35(3):219-223.
[66]邱卫东,陈燕等.一种实时异构嵌入式系统的任务调度算法[J].软件学报,2004,15(4): 504-511.
[67] Carpenter, J., Funk, S., Holman, P., Srinivasan, A., Anderson, J., Baruah, S.: A Categorization of Real-Time Multiprocessor Scheduling Problems and Algorithms[Z]. In: Leung, J.Y.-T. (ed.) Handbook of Scheduling: Algorithms, Models, and Performance Analysis, Chapman Hall/CRC Press, Boca Raton, USA (2004).
[68]罗宏伟,吴斌等.快速启发式多约束优化路径算法研究,自动化与仪表[J].2008.9:5-8.
[69] R. Armstrong, D. Hensgen, and T. Kidd. The relative performance of various mapping algorithms is independent of sizable variances in run-time predictions[C]. In 7th IEEE Heterogeneous Computing Workshop (HCW’98), pages 79-87, Mar.1998.
[70] R. Freund, M. Gherrity, S. Ambrosius, M. Campbell, M. Halderman, D. Hensgen, E. Keith, T. Kidd, M. Kussow, J. Lima, F. Mirabile, L. Moore, B. Rust, and H. Siegel. Scheduling resources in multi-user, heterogeneous, computing environments with SmartNet[C]. In 7th IEEE Heterogeneous Computing Workshop (HCW’98), pages 184–199, Mar. 1998.
[71] R. F. Freund and H. J. Siegel. Heterogeneous processing[J]. IEEE Computer, 26(6):13–17, June 1993.
[72] O. Ibarra and C. Kim. Heuristic algorithms for scheduling independent tasks on nonidentical processors[J]. Journal of the ACM, 77(2):280–289, Apr. 1977.
[73] Thomas S , Holger H H.MAX-MIN ant system [J]. Future Generation Computer Systems(S0167-739X),2000,16(8):889-914.
[74] Stiitzle T,HoosH.MAX-M IN an t system an d loc al search fur the traveling salesman problem [C].In Proceedings of the 1997 IEEE International Conference on Evolutionary Computation.New York: IEEE Press,1997:309-314.
[75] Temlyakov V N.Greedy algorithm with regard to multi-variate systems with special structure[J].Constr. Approx, 2000,16:399-425.
[76] Kavitha S. Golconda, Füsun ?zgüner, Atakan Do?an, A Comparison of Static QoS-Based Scheduling Heuristics for a Meta-Task with Multiple QoS Dimensions in HeterogeneousComputing[C]. In Proceedings of the 18th International Parallel and Distributed Processing Symposium (IPDPS'04) Santa Fe, New Mexico 2004:106.
[77] ZHANG Jinquan, NI Lina, JIANG Changjun. A heuristic scheduling strategy for independent tasks on grid[C].In: Proceedings of the 8th International Conference on High-Performance Computing in Asia-Pacific Region. Los Alamitos, Cal. , USA: IEEE Computer Society, 2005 : 588-593.
[78] Ding, Ding; Luo, Siwei; Gao, Zhan.A Dual Heuristic Scheduling Strategy Based on Task Partition in Grid Environments[C]. In: Proceedings of International Joint Conference on Computational Sciences and Optimization, 2009:63-67.
[79] H. Singh and A. Youssef. Mapping and scheduling heterogeneous task graphs using genetic algorithms[C]. In 5th IEEE Heterogeneous Computing Workshop (HCW’96), pages 86-97, Apr. 1996.
[80] L. Wang, H. J. Siegel, V. P. Roychowdhury, and A. A. Maciejewski.Task matching and scheduling in heterogeneous computing environments using a genetic-algorithm-based approach[J]. Journal of Parallel and Distributed Computing, 47(1):1-15, Nov. 1997.
[81]钟求喜,谢涛,陈火旺.基于遗传算法的任务调度与分配[J].计算机研究与发展,2000,37(10):1197-1203.
[82] Back, T.,Evolutionary Algorithms in Theory and Practice[M]. Oxford university Press, New York, 1995
[83]纪树新等,遗传算法在车间调度中的应用[J].系统工程理论与实践,1998,18(5): 34-39.
[84]刘勇,康立山等,非数值并行计算(第二册)——遗传算法[M],北京:科学出版社,1995.
[85]王凌,郑大钟,基于遗传算法的Job Shop调度研究进展[J],控制与决策,2001,11(16): 641-645.
[86]王凌编著,车间调度及其遗传算法[M],北京:清华大学出版社,2003.5.
[87] Edwin S H,Hou Nirwan An sari.Genetic algorithm for multiprocessor scheduling [J].IEEE Trans on Parallel and Distributed Systems(S1045-9219), 1994,5(2):113-120.
[88]马学彬,温涛等.一种基于遗传算法的网格任务调度算法[J].东北大学学报(自然科学版).2007,28(7):973-977.
[89]钟求喜,谢涛,陈火旺.基于遗传算法的任务分配与调度[J].计算机研究与发展,2000,37(10):1197-1203.
[90] M. Coli and P. Palazzari. Real time pipelined system design through simulated annealing[J]. Journal of Systems Architecture, 42(6-7):465–475, Dec. 1996.
[91] S. Kirkpatrick, J. C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science[J]. 220(4598):671–680, May 1983.
[92]刘勇,康立山等,非数值并行计算(第一册)——模拟退火算法[M],北京:科学出版社,1994
[93] Hironori Kasahara.Seinosuke Narita Practical multiprocessor scheduling algorithms fur efficient parallel processing[J].IEEE Trans on Computers(S0018-9340),1984, 33(11) :1023-1029.
[94] Armastrong R,Hensgen D,Kidd T. The relative performance of various mapping algorithms is independent of sizable variances in run-time predictions [C]In: 7th IEEE Heterogeneous Computing Workshop.Washington D.C: IEEE Computer Society. 1998: 79-87.
[95] Freund RF, Gherrity M, Ambrosius S, et a1. Scheduling resources in multi-user, heterogeneous,computing environments with Smart Net[C] In:7th IEEE Heterogeneous Computing Workshop.Washington D.C:IEEE Computer Society.1998:184-199.
[96] Xu Zhihong,Hou Xiangdan ,Sun Jizhou.Ant Algorithm- based Task Scheduling in Grid Computing[C]. IEEE Canadian Conference on Electrical and Computer Engineering. Washington D.C: IEEE Computer Society,2003:1107-1110.
[97]段海滨.蚁群算法原理及其应用[M].北京:科学出版社, 2005.
[98]汪镭,吴启迪.智能蚁群算法及应用[M].上海:上海科学技术出版社, 2004.
[99] Dorigo M, Gambardella LM. Ant Colonied for the Traveling Salesman Problem [J].Biosystems(S0303-2647),1997,43(2):73-82.
[100] Stiitzie T,Dorigo M.ACO Algorithms for the Quadratic Assignment Problem [C]. New Methods in Optimization.London:McGraw-Hill,1999:3-50.
[101] Colorni A,Dorigo M.Ant System for Job-shop Scheduling [J].Belgian Journal of operations Research,Statistics and Computer Science(S0770-0512), 1994, 34(1):39-53.
[102] Schoonderwoerd R , Hollan d O, Bruten J, et a1. Ant-based Load Balancing in Telecommunications Networks [J].Adaptive Behavior (S1059-7123),1996,5(2):169-207.
[103] Lian g Yc.Smi th Ae.An Ant System Approach to Redundancy Allocation[C].In: Proceedings of the 1999 Congress on Evolutionary Computation,Piscataway.New York:IEEE Press,1999:1478-1484.
[104] Clerc M.Discrete Particle Swarm Optimization , Illustrated by Traveling Salesman Problem[M ].Berlin:Springer-Verlag,2004.
[105]冯斌,孙俊.一种多处理机任务分配的启发式算法[J].计算机工程,2004,30(14):63-65.
[106] Kennedy J,Eberhart R C.Particle Swarm Optimization [C].In: Proceedings of the IEEE International Conference on Neural Networks.Perth,Australia:[s. n.],1995:1942-1948.
[107] Kennedy J,Eberhart R C A Discrete Binary Version of the Particle Swarm Algorithm[C]. In: Proceedings of the World Multi Conference on Systems, Cybernetics and Informatics. Piscataway, Nagoya,Japan:IEEE Service Center,1997:4104-4109.
[108]高尚,杨静宇.多处理机调度问题的粒子群优化算法[J].计算机工程与应用,2005,41(27):72-73.
[109]王凌.智能优化算法及其应用[M].北京:清华大学出版社,200l.
[110]王凌,刘波著.微粒群优化与调度算法[M].北京:清华大学出版社,2008.
[111] Min-You Wu, Wei Shu, Zhang, H. Segmented Min-Min: A Static Mapping Algorithm for Meta-tasks on Heterogeneous Computing Systems[C]. Proceedings of the 9th Heterogeneous Computing Workshop(HCW 2000):375-385.
[112] K.Rameshkumar, R.K. Suresh, and K.M.Mohanasundaram: Discrete Particle Swarm Optimization (DPSO) Algorithm for Permutation Flowshop Scheduling to Minimize Makspan[C]. In: Proc. ICNC 2005, LNCS 3612, (2005):572-581.
[113]钟一文,杨建刚.独立任务分配问题的离散粒子群优化算法[J].模式识别与人工智能,2006,19(3): 399-405.
[114]陈养平,王来雄,黄士坦.基于粒子群优化的多处理器任务调度算法[J].吉林大学学报(信息科学版), 2007, 25(3): 277-285.
[115] Peng-Yeng YinT, Shiuh-Sheng Yu, Pei-Pei Wang, Yi-Te Wang.A hybrid particle swarm optimization algorithm for optimal task assignment in distributed systems[J]. Computer Standards & Interfaces. 2006,28(4): 441-450.
[116] Tasgetiren MF, Liang YC, Sevkli M, Gencyilmaz G. A particle swarm optimization algorithm for makespan and total Flowtime minimization in the permutation flowshop sequencing problem[J]. European Journal of Operational Research. 2007,177(26):1930-1947.
[117] H. Chen and A. M. K. Cheng, Applying Ant Colony Optimization to the Partitioned Scheduling Problem for Heterogeneous Multiprocessors[J]. ACM SIGBED Review, 2005,2(2):11-14.
[118] Liang-Teh Lee, Hung-Yuan Chang, Kang-Yuan Liu, etc. A Dynamic Scheduling Algorithm in Heterogeneous Computing Environments[C]. International Symposium on Communications and Information Technologies, 2006: 313-318.
[119]王堃,乔颖等.实时异构系统的动态调度算法研究[J].计算机研究与发展, 2002,39(6):725-730.
[120]杨玉海,宾雪莲等.异构实时多处理器系统的动态调度算法研究[J].小型微型计算机系统, 2008, 29(1):130-134.
[121] Zhang Jie, Yang Fumin, Tu Gang. A Dynamic Scheduling Model for Real-Time Tasks in Reliable System[C]. In Proceedings of the 2009 International Conference on Networks Security, Wireless Communications and Trusted Computing,2009:185-188.
[122] A novel dynamic allocation and scheduling scheme with CPNA and FCF algorithms indistributed real-time systems[C]. Proceedings of the 11th International Conference on Parallel and Distributed Systems(ICPADS '05):550-556.
[123]丁丁,罗四维,高瞻.一种基于任务划分的启发式网格调度策略[J].北京交通大学学报,2007,11(5):72-76.
[124]周双娥,袁由光等.基于任务复制的处理器预分配算法[J].计算机学报,2004,27(2):216-222.
[125]姚文胜,薛广涛等.基于任务复制的进化调度算法[J].上海交通大学学报, 2004,36(5):755-762.
[126]林剑柠,吴慧中,陈学勤.基于任务复制的网格任务调度算法[J].计算机科学, 2006,33 (6): 89-105.
[127] Wang Q, Cheng K. H, List scheduling and parallel tasks [J]. Information Processing Letters, 1991, 37(5):78-87.
[128] Darbha S., Agrawal D. P. . Optimal scheduling algorithm for distributed-memory machines[J].IEEE Transactions on Parallel and Distributed Systems,1998, 9(1):87-95.
[129] Park Chan-Ik, Choe Tee-Young. An optimal scheduling algorithm based on task duplication[J].IEEE Transactions on Computers, 2002,51(4):444- 448.
[130] Gerold J?ger, An Efficient Algorithm for Graph Bisection of Triangularizations [J]. Applied Mathematical Sciences, 2007,1(25):1203-1215.