組合せ最適化問題に基づいた 低消費電力タスク・スケジューリング

情報処理学会第 74 回全国大会
4M-4
!"#$%&'()*+,./01234564789:;<=6>?@;AB
CD EF†! GH IJ‡
KLKMKMNOPMQRSOPMTU† KLKMOPMVOPW4XBMS‡
!" #$%&!
! YZ[\]^_`abcde)fg/012
ahij'(klmn,gopa-q/012
rstugvwlxyjz{|}n,gopa
~•€\]^_`a•‚ƒ„…r.†‡#gˆ
k • / 0 1 2 r s t u g DVFS (Dynamic
Voltage Frequency Scaling)k,‰Š‹rŒ•Ž
-34564789:;<=xyj••‡}n
,g[1,2]o‘’•“./0123456478
9:;<=r345)•‚ƒ„…r”•–ng
!"#$%&'(kŽnk|{[345=—˜
r™…a345š)›”Ž[œ345š)›•
žŸyr%•ugˆk•$% r¡¢ugxy
r••ugo345=—˜r ETF l£J¤¥l
4789:;<=6>?@;AB•4789:
;<=Ž-¦§) DVFS r%•Ž-¨"a$%
r¡¢ugˆkr©¥kugo
'" ()!
! DVFS k“\]^_`a•‚ƒ„…k•‚1
ªa!•«‡}g P-State r[\]^_`a•‚
~)•¥)¬-ugˆk•/012rstug
Š‹•®g[3]o‘’•“ AMD ¯°a Athlon64
3000+\]^_`rŒ•ugoˆa\]^_`)
“ P-State j 3 ±²•³‡}n,goP-State r
¬-‡#gˆk•[\]^_`a•‚ƒ„…r
1/2 ´•.†‡#[/012r 1/4 ´•stug
ˆkj•µgo¶ 1 )·r¸uo=—˜a¹º
j»¼½¾[¿ºj/012r«Žn,go(b)
•“(a)f•€\]^_`a»¼ÀÁj 1/2 kl
•»¼½¾j 2 Â)lgj[/012“ 1/4 •®
goŽ-jmnÃ_ÄV›aÅÆ[ulÇÈ/
012ÉrÊËugk(b)aÌjÍlÎlgoŽ
-jmnÏн¾)ÑÒj®g¨"[DVFS )
f•(b)aÓÔ•\]^_`r•‚‡#-ÌjÕ
Öj×,oDVFS r•,-./0123456
4789:;<=“[œ345aÏн¾rz
{[P-State a¬-jØcl345rÙÚugˆ
k•/012Érstugo
*" +,-./!
! e•ÛÜ-f‰)[\]=—BÝÞa»¼½
¾rhi‡#l,f‰œ345) P-State r”•
–n[/012rstugaj[./034
564789:;<=a©¥•®go345…
Fig.1 Power Consumption and execution time
r n[P-State a…r P kugkˆa ß¾“
Pn kl•[345…jhiugk$% ràq
gˆkjáâ•®go‘’•“ˆa'(rœ3
45)$%l P-State r”•–ng!"#$%&
'(kz{go!"#$%&'(k“[ãKl
¡¢Éräå'(rstugæ[´-“çèr
é-uê'(r Έk•$× ràqg'(
• ® g [4] o ë ) ˆ a ' ( • “ [ ® g 3 4 5 )
DVFS r%•ugkìaíÎa345)paî
ïrðñua•[J¤¥l!"#$%&'(a
yr%•ugˆkjâŽ,o
! ‘’•“ãKl¡¢Érstug-q345
=—˜ròåæa345š)›”Ž[›”Ž345š)óŽn!"#$%&'(a*‘ôõ
aJå•®g›•žŸyr%•ug>\]:Ä
rö•ugo›•žŸyk“[pa'(a†÷
øùe÷ør›•çèkŽnúŸŽ[paçè
)"Çl,û3:<“üýugˆk•¡¢Ér
stugxy•®g[5]o‘>\]:Ä•“[PState r%•Ž-kµ)\]=—BÝÞaþÿ½
¾jhiŽ-¨"û3:<rüýugk,‰›
•çèr•,go
! 345=—˜r,Îåæa345š)›”Ž[
¡¢ugˆk•¡¢Éastj!"•µgj[
345ša#$)“%³j&'•®go®g3
45š(a DVFS a%•jìa345š)îï
r){l,f‰l345›”jÿ*+j[,»
¥)“âŽ,o®g345) P-State r%•Žˆk•»¼½¾j-. [ìa345a»¼/0
½¾j1Îlm-kugoˆakµ/0½¾j
1Îlm-345)%••µg P-State j[/0
½¾j1Îlg2kLv•®gkµ[ˆ}|a
345“34“Žn,gj DVFS %•)fgî
ïjÍlÎêa345škŽn56)óþ•µ
gkz{|}go7)þÿ"Ƚ¾r89 ug
1-467
Copyright 2012 Information Processing Society of Japan.
All Rights Reserved.
情報処理学会第 74 回全国大会
!"#$%&[1,2]' DVFS ()*+,-./0
1234567 2 8!"#$%&*9-:;6
7<*#$% n3=n7 '>?@ABC-DEFG6
;FHAIJKLBC-MNOPQRSTU/
FGS;Q6R*S/=!"#$%& A *#$
% n1=n2 '#$% n2=n3 C8VW;Q>?@A
BC-XY;Q6ZE=!"#$%& B U[\
]8#$% n5=n6 C=n6=n7 C*>?@ABC
-XY;Q6!"#$%&U'>?@ABCXY3^GQE_=!"#$%&8`3^GQ
Gabc*#$%8 DVFS -()3ES/=X
Y3^GQ>?@ABCTde;QE_=+,
T./GSfgQ6
!" #$%&'(!
! hi*jkl-fm3Enopqr$stu
vwxyz{|}w~•-h€8•‚Q6ƒ„
*#$%8…3^ DVFS -()3ES/=†#
$%* P-State T‡ˆ3E‰Š‹=!"#$%&
S3^Œ•3^GQ‰Š=RbŽ-#$%&S
3^•!•‘;Q6R*•!•‘-’#$%U
J5RSU=G0“c*”•#$%&S=–*
#$%S[•!•‘ObFc—E˜”•#$%
&-™š;Q6ZE=›”•#$%&8…3^
œ•=DVFS -()3E‰Š* P-State -žŸ
3=\]* ¡-J56R*S/=†*”•#
$%&8`3^GQ#$%T¢£S3^¤¥3
E‰Š=¦*”•#$%&S§Š-J56¨©
8˜”•#$%&8…3^˜”•#$%&8`
3^GQ<Uª«T¤¥3^GQ#$%-#$
%&S3=DVFS -()3E‰Š* P-State žŸ3¢£T¤¥3E‰Š=•!•‘3=†*
”•#$%&8`3^GQ‰Š'§Š;Q6¨
¬-8•!•‘ObFc—E#$%-’^=#
$%&S3^”•#$%&*®“8;Q6hi
* ¡8¯°±²*”•#$%&8”•3=”
³´µ¶-();QRSU·*™š-J56
)" *+,-!
! ¸I¹U'”³´µ¶-)G^º»¼¶*½
¾ ¿ À - J 5 6 Á  u à Á Ä v x 8 ' AMD
Athlon64 3000+ÅÆÇÈÉT 8 ƒÊËObEÉ
vÌžŸÍ-ε;Q6$stuvwxy…Ï
S3^ STG (Standard Task Graph set)[6]cŽ
”³´µ¶UžŸÐ¾F#$%² 20 *#$%y
ÑÒ 180 ÓÔ-¡Œ3^Õ);Q6STG U'ª
« Ö $ × ' Ø µ O b ^ G F G E _ CCR
(Communication to Computation Ratio)[7] *
0.1 -Õ);Q6CCR 'ª«>?*ÙÚU4°
0.1 U'ª«TeFGÛÜSµÝOb^GQ6h
i*ÁÂuÃÁÄvxÛÜ- Intel Xeon E5430
2.5GHz=Þßw 8GB * Linux àv%$ávÁ
Fig.2 Connection Task Group
! Tabel 1 Experimental results
žŸâ•[sec]
opqrã[W*ut]
”³´µ¶
º»¼¶
32835.38
728656
235.07
728656
Äxi8äå3E6
! #$%”•-JHa8”³´µ¶-)GQ‰
ŠS=º»¼¶-)GE‰ŠU=¦*žŸBC
S·S3^æŽbE¨çopqrã-èé;Q6
ÁÂuÃÁÄvx*§ê-ë 1 8:;6I¹§
꯰=”³´µ¶Sº»¼¶UæŽbE¨ç
opqrãT®ì3^GQRST”cQ6#$
%”•-JHFG”³´µ¶U'¨(·TžŸ
U/Q*U=º»¼¶U[¨(·T™šU/^
GQRST”cQ6ZE=º»¼¶*žŸBC
'í 1%SF—^GQ6;‚^*#$%-”³´
µ¶U·0*U'F0=±²*#$%&8”•
3ERSU>?â•Tîi3ESRST”cQ6
." /012!
! DVFS ()8¯Q¨(·™š{|}w~•8
“G^•‚E6¿ÀI¹*§ê=º»¼¶U[
¨(·T™šU/=>?â•*îi-ïð;Q
RSTU/E6ñ©*òkS3^=”•#$%
&*#$%²T 20 -ógQSžŸ8ô.FBC
TccQE_=¯°./G#$%²*#$%y
ÑÒU*žŸõ¶-f»;Qö÷T4Q6
3456!
1. øù®ú,ûüý®,þÿ!":”#$%•#^{|}w~
•8$‘Qopqr%d*E_* DVS()#$%&'
Í ä ”, ( 8 ) * + , - . / Ò0vÑ•
FIT2009,Vol.1,pp.157-164 (2009).
2. øù®ú,ûüý®,þÿ!":”1|2zÅÆÇÈÉ ÛÜ
8$‘QDVS-)GEopqr%d{|}w~•*ä
å”,q3-4567C , Vol.131,No.4,pp926-933 (2011).
3. Hisa Ando:”ÅÆÇÈÉ-8gQ./ –ê^3F0$9
v:-;<;Q=> ”,?@4A./¿5A (2011).
4. ñBC ,DEFG:”H²žI¶SJŠP¨(ˆ ”,K,.
!šLA (1982).
5. MNOP,QERS:”JŠP¨(ˆ –Þ#TU-<VS
3^-“,ûüWX (2001).
6. T.Tobita and H.Kasahara:”Performance Evaluation
of Minimum Execution Time Multiprocessor
Scheduling Algorithms Using Stndard Task Graph
Set”,Proc.of 2000 Int’l.Cong. on Parallel anad
Distibuted Processing Techniques and Applications
(PDPTA),pp745-751 (2000).
7. O.Sinnen:”Task Scheduling for Parallel
Systems”,Wiley-Interscience (2007).
1-468
Copyright 2012 Information Processing Society of Japan.
All Rights Reserved.