|
题6
7 j G6 e9 n- h- o* a' e建设节约型社会要求在社会生产、建设、流通、消费的各个领域,在经济和社会发展的各个方面,切实保护和合理利用各种资源,提高资源利用效率,以尽可能少的资源消耗获得最大的经济效益和社会效益。近年来,能源紧缺问题日益突出。尽管单台计算机功率不大,但总的数量增长十分迅速。据统计,1998 年在美国计算机消耗了13%的电力供应。CPU 节能的另一个动因来自笔记本电脑、智能手机等靠电池供电的电子设备上。为了延长电池使用时间,必须尽可能地减少能量消耗。
8 Z; v: K7 O3 m# s# ^: z一般说来,单位时间CPU 能耗与CPU 在该时刻的工作率有关,工作率越大,能耗越高。而工作率又影响设备的性能,决定程序的反应时间和完成工作所需的时间。当然不同情况下,侧重有所不同。以下是两类常见的问题。 ( Q$ U. h3 t$ a% c3 d% ^4 I( g1 w/ f
问题一:现有一批任务,每个任务有其到达时刻和截止时刻,任务必须在两者之间完成,但允许在多个不连续的时间区间内运行,CPU 在同一时刻也可执行多个任务。要求这些任务都可按时完成,并且耗用的能量最小。 * E; m, ~, v+ y. ?* b$ Y
问题二:假设任务只有到达时刻,没有截止时刻,完成这些任务所消耗的能
& a; Q4 n, z% o! R3 ?4 \量有一个上限。要求在耗用能量不超过上限的条件下,使这些任务的流程时间之和尽可能小,这里某个任务的流程时间是指其完成时刻与到达时刻之差。
2 N5 u/ G' q/ O8 L1 c6 f4 v对以上两个问题,试作出合理的假设,建立模型,设计算法以给出CPU 如何处理一批任务的方案,并分析你的算法的性能。 5 ~- T" U; n% q& M3 ?9 _( ^
下面给出一组简单数据用于问题一的测试,你的算法应能处理更复杂的情况。假设CPU 每秒最多可完成1000 万个单位的运算,到达时刻与截止时刻单位均为秒。
8 S; h" a: w$ r+ s
% W$ G5 R( a/ ~任务序号 % G/ ^/ Z* f( ~0 x
| 1
5 P8 z/ R0 ]3 D, b. a* F | 2
3 n" M# ?: X+ ~+ w | 3 - T( `2 L% r$ r- Y$ t) Y; `2 ~
| 4 ' m" b# @; t( u# j" H2 q$ Y4 R
| 5
& L6 U ^1 s; Z! U4 s | 6 4 `- l9 P6 u. k- \/ C( ]: g
| 7
5 S8 ^ k- C* K: m/ m | 8 $ G k, O2 w1 q, P4 e
| 9
& H# w# l! J% T5 D, Q | 10
* i7 x5 x, Q9 p! v& \0 M | 11 ) h' `# R1 D/ a
| 到达时刻 ; O+ E9 O+ g6 p: A5 ~1 F3 a
| 0 & _% N* z8 |. L& \$ T2 G
| 1
4 V* Z% A; |6 N2 s3 ~ | 1
: D6 m; c5 h# A/ A, a | 2
: { {/ ^5 L" h7 F | 4
7 V4 G: `+ H: _3 ~1 Y | 5 % Y0 z1 z1 ?) c3 H% ]4 i! ~
| 8
8 ^8 j* G2 ^+ V3 R0 t | 7 4 ~$ A5 x2 x8 n3 ~
| 7 ! y. T! N/ Y4 t+ t }
| 8 $ C" C3 J& B+ ?0 \+ O8 Y1 ^ ]
| 5 : W% D* b6 v: Y2 Z" U8 h4 L
| 截止时刻 2 R' x( j, |/ C& ~. Y2 y$ o
| 2
; E& p$ p( i0 m' u6 m# C | 2
) U9 b2 r1 Z* Z4 q" N/ l- Q | 3 ' x1 R+ s5 B0 ^5 f) [
| 5 2 M2 @8 h3 `. R1 b' K
| 8
% P0 ^$ r- r+ X8 G | 7 ! ?3 ^: J) G$ G& l7 z( J, C* \
| 9
& H7 v/ ?' v) V$ u$ X% N% W | 8 ' l2 m; P' ~6 M3 C" ^
| 9
% B8 r% A- t& v7 a5 C | 10
5 @ W7 `* r% y! {$ W3 B5 Z7 T7 ~ | 10 + [; F7 w, U( h" E: i* L( g
| 所需运算单位数(百万)
) I8 v9 U/ m2 A4 W2 G | 3
+ E ]7 e# d4 c, C; n6 [ | 6
- S4 U% }1 O# t | 9
2 c; B7 V; f# m6 L b. U | 6 , y& z7 L# z, ]2 g3 x% r
| 12 " a" y5 o1 @) t
| 6
" [" S3 n: x" C3 N3 _( E9 B | 3
0 [) s9 a7 K0 A2 \ | 9
- Q& Q8 q# W1 B& q/ R: {9 D4 a% L3 r | 6
3 |* M+ t5 r. B5 k4 t$ ]/ d | 3
, J: v1 d$ @* a0 b& n _ | 3
/ \3 S% w- Z0 D/ C+ I+ l' \ |
, I% z0 D% C; |* m% Y" h
, {6 o: R# d- D2 X/ o0 f" P* c- r) U有知道答案的吗?或者给我一点思路 急求!后天就要交了~ 相关文献也可以,谢谢了 |