|
题6
" ?; N H0 _% j. I8 P0 _建设节约型社会要求在社会生产、建设、流通、消费的各个领域,在经济和社会发展的各个方面,切实保护和合理利用各种资源,提高资源利用效率,以尽可能少的资源消耗获得最大的经济效益和社会效益。近年来,能源紧缺问题日益突出。尽管单台计算机功率不大,但总的数量增长十分迅速。据统计,1998 年在美国计算机消耗了13%的电力供应。CPU 节能的另一个动因来自笔记本电脑、智能手机等靠电池供电的电子设备上。为了延长电池使用时间,必须尽可能地减少能量消耗。
2 K% d2 D3 q1 _1 ]) w$ v4 ^一般说来,单位时间CPU 能耗与CPU 在该时刻的工作率有关,工作率越大,能耗越高。而工作率又影响设备的性能,决定程序的反应时间和完成工作所需的时间。当然不同情况下,侧重有所不同。以下是两类常见的问题。 3 @' O" o/ n9 A* f' v- e/ l. m
问题一:现有一批任务,每个任务有其到达时刻和截止时刻,任务必须在两者之间完成,但允许在多个不连续的时间区间内运行,CPU 在同一时刻也可执行多个任务。要求这些任务都可按时完成,并且耗用的能量最小。
8 D) ~ U, f& B! U( ]问题二:假设任务只有到达时刻,没有截止时刻,完成这些任务所消耗的能
+ H H8 I: Z l量有一个上限。要求在耗用能量不超过上限的条件下,使这些任务的流程时间之和尽可能小,这里某个任务的流程时间是指其完成时刻与到达时刻之差。 9 P- V+ k& ]0 ^. Z1 T& l( V
对以上两个问题,试作出合理的假设,建立模型,设计算法以给出CPU 如何处理一批任务的方案,并分析你的算法的性能。
# d/ d0 F0 @& z& e9 W) z9 L下面给出一组简单数据用于问题一的测试,你的算法应能处理更复杂的情况。假设CPU 每秒最多可完成1000 万个单位的运算,到达时刻与截止时刻单位均为秒。 / R! c! g7 n9 j. |
) q: u! v R+ s( R' e' Q; \3 S
任务序号
, ` ]3 x) Z7 w% H8 T2 A7 x | 1
% F1 r- {* p1 X1 d | 2
: \& O; k F5 ^1 `3 X | 3 % t9 K( Y5 q- O0 \
| 4
3 |4 e! ~4 W5 @$ q | 5 - o' n9 ^& H9 u: M9 d0 v
| 6 ! L" o5 m0 z' T8 n4 `9 k
| 7 ) r, H7 E6 U: V b7 T
| 8 # b# h9 J0 r9 B7 F
| 9
) j# m! _7 S, k/ f- i9 f6 r | 10 ) ?9 Q6 q; q) r- A% h2 ?' ]" m
| 11
- c$ K7 y! O/ p% M* i | 到达时刻 0 _+ Q. w9 s3 K
| 0 2 Q+ K% s- F- w2 p: \
| 1
; |# |0 @; M# M5 I- T | 1
/ J3 W4 a6 H* u) J S | 2 ; X% [, ~8 X$ {1 p. q! @2 p
| 4 : d, z/ c1 N8 d" b, [, Z6 P; Q N
| 5
; |6 ]5 J0 G* T" ^' t | 8 8 b) D, V- N" |. V' g5 N
| 7
/ S, g0 h! ^- N | 7 , {( a, [ q! R, |# Z- e8 q( H
| 8
5 ~* d: J% n$ L L& }7 E | 5
/ N* ?/ h$ ]3 M5 a- o$ P* R9 b | 截止时刻 6 Z. o. n8 ^1 u `
| 2 4 A+ f1 L: A$ p* o$ ]7 F
| 2
# i9 C9 ~$ F. }' R | 3
4 \0 [, w. l3 u# [, ^ | 5
+ I+ _6 |$ t y' O' \* n$ _) i | 8
8 V( _& a2 G& m2 O% n! N/ N6 l | 7 ) K# h' p/ B1 a2 d
| 9
1 @4 ]5 T5 ? s | 8 : X P5 t3 M" O7 N, `8 e; D) H
| 9
4 u0 o+ f; R; W# x g; K | 10
6 n0 ^- f9 L. h; I | 10
! P+ W) g8 H- @ | 所需运算单位数(百万) / `$ _" V# K; J! h2 R% k! Y2 b
| 3
! n. `2 v* L: t* D8 ]' f, T | 6
, F6 z( Q r, _' v& M5 i | 9
a( W3 M1 L& t1 ^$ c Q | 6
% q' V& s! n) T9 Y) ]3 j | 12
0 O' P; O& Y S6 x$ Z | 6
6 y4 P' J8 @0 K+ R( H: H0 n | 3 $ Y, C0 K a1 P9 M
| 9 n$ N- e4 g0 v- s
| 6 8 u* W1 c$ S2 m" g& a- L4 `
| 3
) p$ t7 D) [. g; K: r" t | 3
! D I- ?8 y0 ~; K. s/ o | 1 ^. p) i4 m7 y1 i0 e
5 o: h* g0 y* n1 q( |" ]有知道答案的吗?或者给我一点思路 急求!后天就要交了~ 相关文献也可以,谢谢了 |