没有合适的资源?快使用搜索试试~ 我知道了~
资源推荐
资源详情
资源评论
第 35卷 第 3期
2012年 3月
计 算 机 学 报
CHINESE JOURNAI OF COMPUTERS
Vo1.35 No. 3
M ar. 2O12
非对称多核 处 理 器上 的操 作 系统集成 调 度
陈锐忠 齐德昱 林伟伟 李 剑
(华南 理工 大学 计算 机系 统研究 所 广州 510006)
摘 要 相对 于对称多 核处理器 ,非对 称多 核处理 器具 有 更 高的效 能 ,将 成为 未来 并行 操作 系统 中的主 流体系结
构.对于 非对称多核 处理器 操作 系统 的并行任 务调 度问 题 ,现有 的研究假设 所有核 心 频率恒 定 ,缺 乏理论 分 析 ,
也没有考虑算 法 的效 能和通用性 .针对该 问题 ,该 文首先 建立 非线性 规划模 型 ,分析得 出全 面考虑 并行任 务 同步特
性 、核心非对称 性以及核心 负载的调 度原则.然 后 ,基 于 调度原则 提出一个 集成调度 算法 ,该算 法通 过集 成 线程调
度 和动态 电压频率 调整来提高 效能 ,并通 过参数调整 机 制实现 了算 法 的通 用性.提出 的算 法是第 一 个在非 对称 多
核处理器上结 合线程调度 和动态电压 频率调整的 调度算 法.实际 平台上的实 验表 明:该 算法可适 用于多种环 境 ,且
效 能 比 其他 同类 算 法高 24 ~50 .
关键 词 绿色计算 ;非对 称多核处 理器 ;操作系 统调度 ;并 行任务调度 ;动态 电压频率调整 ;负载均衡
中 图法 分 类号 TP316 DOI号 :t0.3724/SP.J.1016.2012.00616
Integrated Scheduling for Operating System s on Asym m etric M ulti-core Processors
CHEN Rui——Zhong QI De——Yu LIN W ei——W ei LI Jian
(Institute 0_,Computer Systems,South China University oJ Technology,Guangzhou 510006)
Abstract Asym metric multi—core processors (AM P) are m ore energy efficient than sym metric
m ulti—core processors(SM P)and will be the mainstream of parallel computing architecture in the
future. The existing researches on the problem of parallel task scheduling in operating systems
(0S)on AM P assum ed all cores have constant frequencies. They haven’t analyzed the problem
theoretically. These researches took neither the energy efficiency nor the universality of the
scheduling into account. To solve this problem ,a scheduling model based on nonlinear program—
ming is proposed in this paper. M oreover,scheduling principles of comprehensively considering
synchronization characteristics of parallel tasks,asymm etry and load of cores are analyzed and ad
hered. An integrated scheduling algorithm are also proposed based on the m ode1. The algorithm
integrated thread scheduling and dynamic voltage and frequency scaling (DVFS)in OS to im prove
energy efficiency. In addition,the algorithm achieved universality with a flexible param eter ad
j ustment mechanism.It is the first algorithm to exploit thread scheduling and DVFS on AMP
sim ultaneously. The evaluation on real platform demonstrates that the algorithm is universal for
different conditions and it always outperforms other scheduling algorithm s on asymm etric m ulti—
core processors(by 24 ~ 50 ).
Keywords green computing; asym metric m ulti—core processors;OS scheduling; parallel task
scheduling;dynam ic voltage and frequency scaling;load balancing
收稿 日期 :2011-08—11;最终修改稿收到 日期 :2012 01 20.本课题得到 国家 自然科学基金 (61070015)、广东省中国科学 院全面战略合作项
目(2009B091300069)资助.陈锐忠 ,男,1985年生 ,博士研究 生 ,主要研究 方向为计算 机体系结构 、系统软件.E—mail:chen.rz02@mail.
scut.edu.cn.齐 德昱 ,男 ,1959年生 ,博 士 ,教授 ,博 士生 导师 ,主要研 究领 域为 计算 机体 系结构 、软件 体系 结构 、计算 机 系统 安 全.林伟 伟 ,
男 ,1980年生,博士,主要研究方向为计算机体系结构 、分布式系统.李 剑,男 ,1976年生 ,博士,讲师,主要研究方向为软件工程 、数据挖掘.
3期 陈锐 忠等 :非对称多 核处理器上 的操作系统集 成调度 617
引 言
IT行业 作 为全球 增长 最快 的行 业 之一 ,其 能耗
也 随着 行业 的增 长 而不 断增 长.文 献 [1]指出 :2008
年 IT设备 总共 消耗 8680亿 度 电 ,占全球 总耗 电量
的 5.3 ;按 照 目前 的增 长趋势 ,到 2025年 ,IT行 业
平均能耗 会达到 2006年的 5倍.能耗问题已成为信
息 系统持 续发 展 的重 大 障碍 .如 何 提 高计 算 机 的效
能 ,实现绿 色计 算 ,是 当今 的一个 研究 热点.
随着 芯 片集 成 规模极 限 的逼 近 以及能耗 和成 本
等 因素 ,多核 处理器 逐渐 占据 了市场 ].相对 于对 称
多 核 处 理 器 (Symmetric Multi-core Processor,
SMP),单 一指 令集非 对 称 多核 处 理器 (Asymmetric
Single—ISA Multi—core Processors,AMP)具 有 更 高
的效能 ,更 符合 绿 色计 算 的 要 求 ,将 成 为 未 来 的主
流 [3 ].现 有操 作 系 统 调 度 器从 单 核 处 理 器发 展 而
来 ,并 为 SMP做 了相 应 扩 展 ,不 能发 挥 AMP 的效
能 优势 .这为 操作 系统调度 带来 了新 的机遇 和挑 战.
随着 多核 技术 的发 展 ,并行 程 序 日益普 及 [2 ].
由于 AMP上 每 个 核心 支 持 同一 指令 集 结 构 ,任 务
可 以在不 同核 心上 正 确 执行 ;而 由于 核心 间 的性 能
异 构性 ,并行 度不 同 的任 务 在不 同核 心 上 的执 行 效
率 却是 不 同 的.如 何 利 用 并 行 任 务 的同 步 特 性 和
AMP的非 对称性 ,实 现 高效 能 的 操作 系统 调 度 ,是
该 形势 下的一 个关 键 问题 .近年 来 有 一 些研 究 关 注
这 一 问题 ,但都 假设 所有核 心频率 恒定 ,没有 建模 分
析 影响调 度 的各个 因 素 ,也没 有 考 虑 算法 的效 能 和
通 用性 ,不能很 好地 解决该 问题 .其 中 :文献 [6]没 有
考 虑任务 的 同 步 特 性 ;文 献 [7]需 要 频 繁 地 迁 移 任
务 ,从 而带 来 巨大开 销 ;文 献 [8]假 设 系统 运 行 的线
程 总数不 大于核 心 总数 ,但 现 实 中这一 假 设 往 往难
以满足.
因此 ,本 文 以效 能和通 用 性 为 目标 ,为 AMP上
操作 系统 的并行 任务 调度 问题建 立 了非线性 规划模
型 ,分析 了任务 的 同步特性 和核 心 的非 对称性 ,得 出
调度 应遵循 4个 原则 :
(1)同一 任务 的各 个 线 程 在 同类 核 心 上 运 行 ,
但不 在 同一个核 心上运 行.
(2)各 核心 负载 均衡.
(3)协 同调 度 同一任务 的各个 线程 .
(4)使 参与协 同调 度 的各 个核 心频 率相 等.
在此 基础上 ,本 文提 出一 个集 成调 度算法 ,其特
点 如下 :
(1)集成 线 程 调 度 和 核 心 动 态 电压 频 率 调 整
(Dynamic Voltage and Frequency Scaling DVFS),
保证 4个 调度 原则 ,提高 系统效 能.
(2)提供 参数 调整机 制 ,以适应 多种 机器 配置.
(3)通过状态 监控机 制和任务集合 分解降低调
度 开销 .
据 我们 所 知 ,还 没有 研究 对 该 问题 进 行 建模 分
析 ,本 文 是 第 一 个 在 AMP 上 结 合 线 程 调 度 和
DVFS的算 法 .本文在 Linux 2.6.27和多 种 配置 的
AMD Opteron 2384上 对 算 法 的效 能 、通 用 性 和 开
销进 行 比较分析 ,实 验证 明 了该算 法 的有效 性.
本 文第 2节对 问题 进行 描 述 和建 模分 析 ,给 出
调 度 的 目标和 原则 ;第 3节详 细描述 集成调 度算 法 ;
第 4节对 所 提 出的算 法 进 行 实验 和 比较 分析 ;第 5
节介 绍 相 关 研 究 ;最 后 是 总 结 以及 对 未 来 工 作 的
展 望 .
2 问题 描述与 建模
2.1 问题 描述
本文 研究 AMP上操作 系统 的并 行 任 务调 度 问
题 ,关 注 的 目标 如下 :
效 能 :最小 化 系统 的 EDP(Energy Delay Prod—
uct) ].EDP 是 系统 的能 耗 与执 行 效 率之 比 ,EDP
越低 ,系 统效能 越高 .
通用 性 :适 用 于核心性 能差 异程度 不 同的 AMP
平 台.
下 面通 过一 个 简 单 的例 子来 说 明该 问题.示 例
中的 AMP包 含 8个 核 心 (如 图 1,图 2):Core ~
Core3是快 核心 ,Core ~ Core8是 慢 核 心 ,快 核 心 的
计算 能力 是慢核 心 的 2倍 .该 平 台 上运 行 4个任 务
(尸0,P ,P 和 P。),每个任 务 包 含 2个 线 程 :丁 和
单位 时间
图 1 现有操作系统调度示例
行
协 砌 靠 靠 “ r r r r r r r
、
0 0 0 0 0 o 0 C C C C C C C C
618 计 算 机 学 报
T2属于 Po, 和 T 属 于 P , 和 T 属于 P ,T
和 Ts属于 P。.每个 线程 优先 级相等 ,属 于同一 任务
的 2个 线程 每隔 2个 单 位 时 间就 要 同步一 次 ,然 后
继续运 行.文献 [7]表 明 :由于 parallel—for、fork—join
等结构 在并行 编程 中 的广泛 使 用 ,并 且 程 序 员倾 向
于平衡 各个 并行线 程 的负 载 ,同 一任 务 的 各 个线 程
计 算量 趋 向于相 等.
图 1给 出 一 个 现有 操 作 系 统 中 的线 程 调度 示
例.现有操 作系统 调度 器没有 考虑 核心 的非对 称性 ,
将线 程 随机 映射 到低 负载 的核 心 上 ,这不 符 合 绿 色
计算 的要 求 :当属 于 同一 任务 的几 个 线程 分 配 到 性
能不 同的核心 上执 行 时 ,将导 致 快 核 心上 的线 程 等
待 慢核 心上 的线程 同步 的情 况 ,此 时 快 核心 仍 在 消
耗 能量 ,从 而 降 低效 能 (如 图 2中 丁 和 T。同 属 于
P。,却 分别 映射 到异类 核心 Core 和 Core 上 ,导 致
等 待 ;P 和 P 亦然 ).
单 位 时 唰
图 2 理想 的操作 系统调度 示例
图 2给 出 了理 想 的操 作 系统 调 度 示 例.(1)它
将 属 于同一任 务 的线程 调度 到类 型相 同的核心 上运
行 ,从 而避 免 了线 程 空 等 的情 况 ,并 将 节 省 下 来 的
CPU 时 间用 于调 度 其 他 线 程 (如 图 2中 的 ),从
而提 高了效 能.(2)当无 法保证 同一任 务 的所 有线
程在 同类 核心 上执 行 时 ,它将 运 行 这 些线 程 的快 核
心频 率 降低 到 与慢核 心相 等(如 图 2中的 Core。),在
不影 响任务 完成 时 间 的情 况 下 降低 了能 耗.本 文 提
出 的调度 算 法 实 现 了这 种 调 度 .下 一 节 将 对 AMP
上操 作 系统 的并行任 务调 度 问题 进行 建模分 析.
2.2 调 度模型
我们 可 以为 AMP上操 作 系统 的并 行 任务 调 度
问题建立非线性规划 模型 :
设 T一 {T ,T。,… ,T ), ∈N ,表 示 一 个 包 含
n个线 程 的任 务 ,所 有 线 程 每 隔一 定 时 间 间隔 需 进
行 同 步 ,线 程 T 可 根 据 同 步 间 隔 分 为 ~ 个 阶 段
{ ,T ,… , t}.每个 阶段可 分为计 算操 作 和 同步
操 作 , .c表示 T 计算 操作 的工 作量 , .st表 示 丁
同步 操 作 所 需 的 时 间.根 据 文 献 [7],本 文 假 设 同
一
任 务 的 各 个 线 程 具 有 相 等 的 计 算 量.C:
{C ,c。,… ,c },n∈N,表示 n个 核 心 的集 合 ,第 i
个 核心 的单位 时 间计算 能 力 为 C .为 了避 免 频 繁 上
下文切 换带来 的巨大 开 销 ,我们 假 设 式 (1)成 立 :一
个 任务 包含 的线程 数 ,不大 于物理 核心 总数 .
T的调度 可抽 象为一 个 时空 映射 M 一(S, ),其
中 S是 一 个空 问 映射 ,表示 将 T 的各个 阶段 映射 到
核心 上 ;t是一个 时 间映射 ,表 示将 T 的各 个 阶段 映
射 到核 心 的 时 间片 上.设 t( )表示 的 开 始 时
间 ,即 分配 到 的时间 片 ,由任 务执 行 的时序 关系 ,
只有 所有 前驱 阶段都 完成 了 ,一个新 阶段 才能 开始 ,
即式 (2)成 立 ,其 中 二 为 T 的计 算 时 间 ,与 执 行
i
的核 心的性 能 C 相 关.Time (T)表 示 映射 M 下
T 的完成 时 间 ,它 等于 T最 后 阶段 中运行 最 慢 线程
的完成 时 间 ,满足 式 (3).EDPM(丁)定义 为系 统 的能
耗 与执行 效 率之 比 ],即式 (4),其 中 Energy—Con—
sumed表示 系统 的总能 耗 ,Instructions—per—Second
表示单 位 时 间 执 行 的 指 令 数 ,Averge—Power表 示
系统 的平 均 功 率 ,Total—Instructions(T)表示 任 务
T指令 总数 .因此 我 们 可得 该 问 题 的非 线 性 规 划 模
型 如 下 :
M inim ize EDP M(T)
I 7’I l C l (1)
)+等 + . } ) (2)
for 0< k,l< l T J and m< n
( r)一 …
k { ( +警 +丁 s£}(3) l , J
EDPM(T)一
1 nstru ctzon s er econd
一 声 一
一
Averge
_
Power X Time ZM(T)
(4)
但 在 现 实 中 由于缺 乏 T7.f和T7.st的先验 知 识 ,
加 上求解该 问题带 来 的 开销 ,无 法 求 得 该 问题 的最
优解 .因此 我们 采用 启发式算 法 来求 问题 的近优 解 .
由于式 (4)中的 Total—Instructions(了、)是定值 ,故最
小 化 EDPM(T)等 价 于 最 小 化 Averge—Power和
TimeM(T).Averge—Power可 通 过 DVFS技 术 。。
动 态调节 ,文 献[4]预测未 来 的 AMP将 由少 量 复 杂
如 岛
剩余10页未读,继续阅读
资源评论
数据资源
- 粉丝: 113
- 资源: 23万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功