《多处理器片上系统任务调度研究进展评述》由会员分享，可在线阅读，更多相关《多处理器片上系统任务调度研究进展评述（10页珍藏版）》请在金锄头文库上搜索。
1、计算机研究与发展ISSN 100021239CN 1121777TP Journal of Computer Research and Development45(9) : 162021629 , 2008收稿日期:2007-08-13 ;修回日期:2008-05-15基金项目:国家自然科学基金项目(60673061) ;国家 “八六三” 高技术研究发展计划基金项目(2007AA01Z104)多处理器片上系统任务调度研究进展评述李仁发 刘 彦 徐 成(湖南大学计算机与通信学院 长沙 410082)(lirenfa vip. sina. com)A Survey of Task Scheduli
2、ng Research Progress on Multiprocessor System2on2ChipLi Renfa , Liu Yan , and Xu Cheng(School of Computer and Communication , Hunan University , Changsha410082)Abstract Multiprocessor is very common in embedded computing systems because it can meet theperformance , cost and energypower consumption g
3、oals.Multiprocessor system2on2chip is oftenheterogeneous multiprocessors and integrates multiple instruction2set processors on a single chip thatimplements most of the functionality of a complex electronic system. Current trends indicate thatmultiprocessor system2on2chip is being increasingly used i
4、n application such as image processing ,network multimedia , embedded system , and so on. Scheduling and mapping of tasks are importantkey problems in multiprocessor system2on2chip design , and are substantially more difficult thanscheduling a uniprocessor. The basic architecture and design challeng
5、e of multiprocessor system2on2chip task scheduling algorithm are introduced.In particular , the current research progresses aresummarized accordingtoschedulingalgorithmanalysisandimplementation framework.Thescheduling algorithm analysis is classified into three categories , and scheduler implementat
6、ionframework is classified into two categories by using task modeling. Many open research problems arepointed out. Because of the large variety of timeliness requirements in real2time applications , animportant goal is to find canonical representations of task considering timing constraints.It is an
7、important targetto implementhigh2effectsschedulerbased onmultiprocessorsystem2on2chipplatform. By comparing and analyzing these different projects and algorithms , researchers of relatedtopic can gain useful information about task scheduling problem.Key words multiprocessor system2on2chip ; real2tim
8、e task scheduling; embedded system ; architectureexploration ; scheduling model摘 要 多处理器片上系统在单芯片上集成了多种指令集处理器,可完成复杂完整的功能,在图像处理、网络多媒体和嵌入式系统等应用领域前景广阔.任务映射与调度是多处理器片上系统设计的关键问题 之一.介绍了多处理器片上系统的基本结构和面临的挑战,从调度算法分析和实现框架两个方面着重探 讨了近年来多处理器片上系统任务调度的国内外研究进展情况,分析了当前亟待解决的问题与下一步主要的研究方向,可为多处理器片上系统相关研究提供参考.关键词 多处理器片上系统;
9、实时任务调度;嵌入式系统;体系结构探索;调度模型中图法分类号 TP316. 4市场对计算平台性能需求的不断提升,使得多 处理器片上系统(MPSOC)成为新一代SOC的主流 设计趋势122. MPSOC一般由多个处理器单元、 专 用功能模块甚至混和信号电路组成,构建一个复杂 的集成计算系统,从而满足市场对于系统在计算性能、 功耗、 实时性与成本等方面的需求. MPSOC不 是简单的片上多处理器(chip multiprocessor) ,后者 强调将更多的处理器放在单片上提高单位面积晶体 管密度,并不考虑平衡应用的需求. MPSOC则通过 定制体系结构来满足不同应用在成本和功耗等方面的需求,已广
10、泛地用于通信、 消费类电子产品和网络 多媒体等诸多领域324. 近年来, MPSOC相关研究引起了广泛的关注, 一些企业和科研院所围绕编程模型、 任务调度、 系统 开发、 调试环境与系统安全等方面开展研究,在IEEE和ACM相关会议上发表了一些重要的研究 成果. 2006年8月14日在美国举行了MPSOC2006会议,进行了多处理器系统芯片设计的理论和 战略研讨. AMD公司在2006年提出了基于 “融合”(fusion)技术的多核处理器产品路线图,其实质是由当前的同构片上多处理器转向更加具有 “硬件加 速器” 概念的异构片上多处理器系统.英特尔、Sun 和IBM等大公司也已投身到多核或者多线
11、程技术 的研发之中,并投入巨资建立了各自庞大的研究计 划.美国斯坦福大学5、 普林斯顿大学6、 威斯康辛大学7等著名学府也一直关注MPSOC相关的研究 工作,启动了一系列的研究计划;法国的TIMA、 新 加坡、 意大利等大学和研究室也发表了相关研究成 果;国内中国科学院、 中国科技大学等也持续跟踪相 关研究.把一个复杂的任务分解,将其映射到异构多处 理器上,满足实时性、 功耗与成本等条件的约束是MPSOC系统设计的关键问题之一.很多任务调度 的研究是基于抽象模型给出任务的形式化定义,然 后进行调度策略与算法的设计.由于多处理器任务调度问题是NP难问题8,改进算法的效率并构建 任务调度实现机制成
12、为研究重点.同时,体系结构上 的异构性使得MPSOC任务调度特别需要关注任务 在不同体系结构的处理单元上执行时的特点,并在 调度器实现上提出了很多新的挑战.本文首先介绍了MPSOC体系结构与关键的设计挑战,然后综述 了MPSOC任务调度领域目前的研究状况,主要针 对实时任务调度的算法分析、 实现机制、 面临的挑战 与亟待解决的问题等方面开展深入讨论.1 MPSOC体系结构与设计挑战1. 1 MPSOC体系结构MPSOC体系结构常用于嵌入式计算系统中,并在性能、 成本和功耗等方面有明确要求,其体系结 构具有明显的异构性,如图1所示.典型的MPSOC 由3类组件组成:处理器单元,包括处理器、DSP
13、或ASIC用于执行计算任务;存储模块用于保存数据; 互连网络用于组件间通信:Fig. 1 MPSOC architecture.图1 MPSOC体系结构异构性是嵌入式多处理器显著的特点,即将计 算能力赋予需要它的地方来满足性能需求,移除不 必要的组件来降低功耗和成本.系统中可以有不同 类型的可编程处理器(如CPU和DSP) ,也可以有 专用处理器单元(如ASIC)来完成单个功能.片上存储结构和通信互连结构也是异构和定制的,从而 满足 嵌 入 式 应 用 在 性 能 和 实 时 性 上 的 需 求.MPSOC在嵌入式应用中已经逐渐展示其强大的生 命力.1. 2 MPSOC设计挑战虽然可从传统的并
14、行计算机系统设计中吸取经 验,但MPSOC在应用中的实际需求使其面临独特 的设计挑战,这仍将困扰MPSOC设计者相当长的 时间.实际上,设计复杂的MPSOC对工程师和学者 带来新的挑战224 ,9210.1)设计方法学: MPSOC设计者需要一种结构 化的设计方法支持系统的设计,从而减少系统设计 时间,并对整个系统的开发周期和资源进行更好的 估计.目前MPSOC设计方法学的研究不断进展,并 在未来随着新技术和工具的出现更加的重要.2)体系结构:包括处理单元、 存储结构和片上 互连方法需要在可编程性与灵活性之间取得平衡. 异构存储结构、 可定制处理器和互连方式逐渐在体 系结构设计中采用,但相关理
15、论研究依然是体系结 构的重要课题.3)编程模型:与传统的顺序编程方式相比,MPSOC更能符合算法的并行处理方式.但分解1261李仁发等:多处理器片上系统任务调度研究进展评述一个顺序描述的应用成为可预测的互相协作的一组 并行任务仍然是非常困难的事情.4)同步与控制: MPSOC中将任务映射到处理 器或者功能单元,任务之间的同步与控制仍具有挑 战.任务的控制是集中式还是分布式,任务间是否有大量的处理器间通信以及优先级翻转、 资源冲突等 问题同样存在.5)系统的调试与工具: MPSOC上运行的任务 使用不同的编程模型和语言,运行在不同结构的处 理器上,任务间通信方式也多种多样,从而使得设计者对整个系
16、统保持一个统一的视角,进行调试,这是 一个非常困难而又急需解决的问题.6)操作系统与中间件: MPSOC平台的操作系 统和中间件应该在代码容量受到限制的情况下,充 分利用异构多处理器的特性进行优化,提供调度、 内存管理、IO和通信管理的同时满足高性能、 实时和 低功耗的要求.7)嵌入式系统安全: MPSOC与网络互连带来 严重的安全问题.此外,对于嵌入式系统应用领域, 通过攻击降低服务质量,从而使得系统失去实时性成为有别于传统安全领域问题的一个新课题.软硬 件结构设计者需要合作研究来提供安全的MPSOC 结构.2 MPSOC任务调度研究进展任务调度是经典问题,很多相关综述11212从各 个角度对其进行了详细的介绍.本文主要关注多处 理器片上系统的任务调度问题,将从任务调度算法 分析和任务调度实现框架两个新的角度总结近年来 嵌入式多处理器计算平台上任务调度相关研究进展.2. 1 任务调度算法分析 任务调度算法分析主要针对抽象任务模型进行 可调度性分析和调度算法设计,提高算法效率和系 统的可调度性是重要问题13.
