ᚑくᄢቇℂᎿቇ⎇ⓥႎ๔
J. Fac. Sci. Tech., Seikei Univ.
Vol.47 No.1 (2010) pp.39-47

ಽᨑ㒢ቯᴺࠍ↪޿ߚ࠲ࠬࠢࠬࠤࠫࡘ࡯࡝ࡦࠣߩߚ߼ߩㅢାࠍ⠨ᘦߒߚਅ㒢୯ߦࠃࠆ㒢ቯᠲ૞ߩឭ᩺Ⴎ↰ 㓉ੑ㧖㧘↲᢫ ቬᓼ㧖

Evaluation of A New Bound Operation Taking Account of Communication Overhead for Task
Scheduling based on Branch and Bound Method
Ryuji SHIODA㧖, Munenori KAI㧖ABSTRACT : The task scheduling technique is the very important key for the efficient parallel
processing. The task scheduling problems belong to the class of NP complete or strong NP complete
combinatorial optimization problem. So in many practical cases, heuristic algorithms are used to solvethem. Taking account of communication overhead into task graphs makes these problems more difficult
to solve by any search algorithms because the search spaces become much larger. In this paper, wepropose, taking account of communication time among tasks, an extended version of original priority
levels used in Critical Path(CP) Method. Priority level of each task is the length of the longest path fromthe task to the last task in the task graph. It is the lower bound of the parallel processing time after thetask. The search is performed by depth first search manner using branch and bound method. By using ournewly proposed priority level as both heuristic and bound operation in the search, it is shown that thescheduling time become shorter than the branch and bound search with the original priority level.
Keywords㧦task scheduling, branch and bound search, heuristic algorithm, combinatorial optimization
problem㧔Received March 25, 2010㧕㧝㧚ߪߓ߼ߦ

ឭ᩺ߐࠇߡ޿ࠆ‫ੱߪࠄࠇߎޕ‬㑆ߩ⚻㛎ߦၮߠߊࡅࡘ࡯࡝
ࠬ࠹ࠖ࠶ࠢࠕ࡞ࠧ࡝࠭ࡓߢ޽ࠅ㧘ᓧࠄࠇߚ⸃߇ᦨㆡ⸃ߢ

ㄭᐕ㧘ࡑ࡞࠴ࠦࠕࡊࡠ࠮࠶ࠨ߿ࡑ࡞࠴ࡊࡠ࠮࠶ࠨߩᛛ

޽ࠆߣ޿߁଻⸽ߪߥ޿‫ߚ߹ޕ‬㧘ోត⚝ࠕ࡞ࠧ࡝࠭ࡓߢߪⴚ߇ะ਄ߒ㧘ਗ೉ಣℂࠍⴕ߁ⅣႺ߇ᐢ߹ߞߡ޿ࠆ‫ޕ‬ℂ⺰⊛ߦߪᦨㆡ⸃߇᳞߹ࠆ߇㧘ታ↪⊛ߥᤨ㑆ߢᦨㆡ⸃ࠍ ਗ೉ಣℂࠍࠃࠅ㜞ㅦߦታⴕߔࠆߚ߼ߦߪ㧘ਗ೉ಣℂࡑᓧࠆߎߣߪਇน⢻ߦㄭ޿‫ޕ‬ࠪࡦߩᜬߟ⸘▚⾗Ḯߩᕈ⢻ࠍචಽߦᒁ߈಴ߔߎߣ߇㊀ⷐߎࠇࠄߩࠬࠤࠫࡘ࡯࡝ࡦࠣࠕ࡞ࠧ࡝࠭ࡓߦߪࠬࠤࠫࡘߣߥࠆ‫ޕ‬ല₸ߩ⦟޿ਗ೉ಣℂߩὑߦߪ㧘ࡊࡠࠣ࡜ࡓࠍ⸃࡯࡝ࡦࠣല₸ࠍᏀฝߔࠆਅ㒢୯ߣ޿߁୯߇ሽ࿷ߔࠆ‫ᧄޕ‬ᨆߒߡਗ೉ታⴕน⢻ߥ࠲ࠬࠢ㓸วࠍ⷗ߟߌ㧘ߘߩ࠲ࠬࠢ⎇ⓥߢߪ㧘ᓥ᧪ߩਅ㒢୯⸘▚ߢ᳞߹ࠆਅ㒢୯ࠃࠅ♖ᐲߩ㓸วࠍਗ೉ಣℂᤨ㑆߇⍴ߊߥࠆࠃ߁ߦߤߩࠃ߁ߦࡊࡠ࠮㜞޿ਅ㒢୯ࠍ᳞߼ࠆ⸘▚ᴺࠍឭ᩺ߔࠆߎߣߢࠬࠤࠫࡘ࡯࠶ࠨ߳ഀࠅᒰߡࠆ߆ࠍ᳿߼ࠆࠬࠤࠫࡘ࡯࡝ࡦࠣ߇ᔅⷐߦ࡝ࡦࠣല₸ߩะ਄ࠍ⋡ᮡߣߒߚ‫ޕ‬ߥࠆ‫ޕ‬ߒ߆ߒ㧘ߎߩࠬࠤࠫࡘ࡯࡝ࡦࠣ໧㗴ߪᒝ NP ࿎㔍ߥࠢ㧞㧚ࠬࠤࠫࡘ࡯࡝ࡦࠣࡕ࠺࡞࡜ࠬߦዻߔ⚵ߺวࠊߖᦨㆡൻ໧㗴ߢ޽ࠅ㧘ߔߴߡߩࠤ࡯ࠬߢᦨㆡ⸃ࠍ᳞߼ࠆᣇᴺࠍᓧࠆߎߣߪ㧘੐ታ਄ਇน⢻ߢ ࠲ࠬࠢࠣ࡜ࡈ޽ࠆߎߣ߇⍮ࠄࠇߡ޿ࠆ‫߼ߚߩߘޕ‬㧘ታ↪⊛ߦᦨㆡ߹ߚ ਗ೉ታⴕน⢻ߥ㧝ߟߩಣℂන૏ࠍ࠲ࠬࠢߣ๭߮㧘࠲ࠬߪㄭૃ⊛ߥ⸃ࠍ᳞߼ࠆࠬࠤࠫࡘ࡯࡝ࡦࠣᚻᴺ߇޿ߊߟ߆ࠢో૕ࠍ࠲ࠬࠢ㓸วߣ๭߱‫ࠢࠬ࠲ޕ‬㓸วߪ㧘࠲ࠬࠢࠍࡁ࡯࠼㧘వⴕ೙⚂ࠍ᦭ะࠛ࠶ࠫߢ⴫ߒߚ㕖ᓴⅣ᦭ะࠣ࡜ࡈ㧖㧦Ꮏቇ⎇ⓥ⑼ᖱႎಣℂኾ᡹ୃ჻ቇ↢ߢ⴫⃻ߢ߈ࠆ‫ߣࡈ࡜ࠣࠢࠬ࠲ࠍࡈ࡜ࠣߩߎޕ‬๭߱‫ޕ‬࿑ 㧦Ꮏቇ⎇ⓥ⑼ᖱႎಣℂኾ᡹ᢎ᝼ (kai@st.seikei.ac.jp)ߪᧄ⎇ⓥߩኻ⽎ߣߔࠆ࠲ࠬࠢࠣ࡜ࡈߩ଀ߢ޽ࠆ‫࠼࡯ࡁޕ‬㧖㧙㧙ߩਛߩᢙሼ߇࠲ࠬࠢ⇟ภ㧘ࡁ࡯࠼ߩฝ஥ߩᢙሼ߇࠲ࠬࠢ

ㅢାࡃ࠶ࡈࠔ߆ࠄㅍࠅవㅢାࡃ࠶ࡈࠔ߳ォㅍߐࠇࠆ‫ޕ‬

ߩಣℂᤨ㑆ࠍ⴫ߒߡ޿ࠆ‫ߚ߹ޕ‬㧘ᧄ⎇ⓥߢߪవⴕ೙⚂ߩ࡮ ࡕ࠺࡞ߣߔࠆ⋧੕⚿ว✂ߢߪ㧘ࡊࡠ࠮࠶ࠨ㑆  ኻ ሽ࿷ߔࠆ㧞ߟߩ࠲ࠬࠢࠍ⇣ߥࠆࡊࡠ࠮࠶ࠨߦഀࠅᒰߡࠆߩㅢାߪ৻ቯࠦࠬ࠻ߢߥߐࠇࠆ‫ ޕ‬ኻ P ෸߮ P ኻ 㓙ߩᖱႎ౒᦭ߦⷐߔࠆㅢାᤨ㑆ࠍ⠨ᘦߒߡ޿ࠆ‫ߚߩߘޕ‬ߩㅢାࠍหᤨೞߦⴕ߁ߎߣߪ⸵ߐࠇߕ㧘ߘߩ႐ว㧘P߼㧘᦭ะࠛ࠶ࠫߦㅢାᤨ㑆߇ઃടߐࠇߡ޿ࠆ‫ޕ‬࿁ߩㅢାࠦࠬ࠻ߩ๺ߛߌ㧘ࠦࠬ࠻߇߆߆ࠆ ࿑  ‫ޕ‬࡮ ৻⚵ߩㅢାߦࠃࠆㅢା⚻〝ߩභ᜚ߪㅢାࠬࡠ࠶࠻ߦ

0 001 6

ࠃߞߡ⴫ߐࠇࠆ‫ޕ‬ㅢାࠬࡠ࠶࠻ߪಽഀߢ߈ߥ޿߽ߩߣߔࠆ‫ޕ‬00ߎߩࠃ߁ߥಽᢔࡔࡕ࡝ဳࡑ࡞࠴ࡊࡠ࠮࠶ࠨࡕ࠺࡞ࠍኻ

2 43 2⽎ߣߒߡ޿ࠆߚ߼㧘ㅢାߩ᦭ήߛߌߢߪߥߊ࠲ࠗࡒࡦࠣ
߽⠨ᘦߒߡࠬࠤࠫࡘ࡯࡝ࡦࠣࠍⴕ߁‫߼ߚߩߘޕ‬㧘࠲ࠬࠢ

112

6 74

4
529 0

ߩࡊࡠ࠮࠶ࠨߦኻߔࠆഀࠅᒰߡߩ⚵ߺวࠊߖߛߌߢߥߊ㧘1⚵ߺวࠊߖߦኻߔࠆ㗅೉߽ࡊࡠ࠮࠶ࠨ߳ߩഀࠅᒰߡࡄ࠲
࡯ࡦߣߒߡ⠨ᘦߦ౉ࠇߥߊߡߪߥࠄߥ޿‫ߦ߁ࠃߩߎޕ‬ㅢାࠍ⠨ᘦߔࠆߣត⚝ⓨ㑆߇ㅢାࠍ⠨ᘦߒߥ޿႐วࠃࠅ߽

2ᐢᄢൻߔࠆߎߣߦߥࠆ‫ޕ‬

17 301



8 4


0





࿑  ࠲ࠬࠢࠣ࡜ࡈ
࠲ࠬࠢࠬࠤࠫࡘ࡯࡝ࡦࠣ໧㗴ߣߪ㧘࠲ࠬࠢࠣ࡜ࡈߩฦ

࠲ࠬࠢࠍਈ߃ࠄࠇߚછᗧߩᢙߩࡊࡠ࠮࠶ࠨߦਗ೉ಣℂᤨ㑆ࠍᦨዊߦߔࠆߎߣࠍ⋡⊛ߦߒߡഀࠅᒰߡࠍ᳿ቯߔࠆߎ࿑  ࡑ࡞࠴ࡊࡠ࠮࠶ࠨࡕ࠺࡞ߣㅢାࠝ࡯ࡃࡋ࠶࠼
ߣߢ޽ࠆ‫ޕ‬㧟 ࠬࠤࠫࡘ࡯࡝ࡦࠣᚻᴺ

 ㅢାߩ࠲ࠗࡒࡦࠣ
 ࡝ࠬ࠻ࠬࠤࠫࡘ࡯࡝ࡦࠣࡊࡠ࠮࠶ࠨ㑆ߩㅢାࠝ࡯ࡃࡋ࠶࠼ࠍ⠨ᘦߔࠆ㓙㧘⋧੕⚿ว✂ߦቢో⚿วࠍᗐቯߔࠆߣ㧘ⶄᢙߩተవߦหᤨߦ࠺

ࠬࠤࠫࡘ࡯࡝ࡦࠣ໧㗴ࠍ⸃ߊࡅࡘ࡯࡝ࠬ࠹ࠖ࠶ࠢࠕ࡞࡯࠲ࠍㅢାߔࠆߎߣ߇น⢻ߣߥࠆ‫ߒ߆ߒޕ‬㧘዁᧪⊛ߥࡊࠧ࡝࠭ࡓߦ࡝ࠬ࠻ࠬࠤࠫࡘ࡯࡝ࡦࠣ߇޽ࠆ‫ࠤࠬ࠻ࠬ࡝ޕ‬ࡠ࠮࠶ࠨ㧔ࠦࠕ㧕ᢙߩࠬࠤ࡯࡜ࡆ࡝࠹ࠖࠍ⠨ᘦߔࠆߣ㧘ࠫࡘ࡯࡝ࡦࠣߣߪ㧘ታⴕน⢻ߣߥߞߚ࠲ࠬࠢࠍⓨ޿ߡ޿ቢో⚿วߪ⃻ታ⊛ߢߪߥ޿ߩߢ㧘ᧄ⎇ⓥߢߪ  ኻ P ߩㅢࠆࡊࡠ࠮࠶ࠨߦഀࠅᒰߡߡ޿ߊᣇᴺߢ޽ࠆ‫ޕ‬ା߇  ኻ  ߩㅢାࠍ P ࿁ㅙᰴ⊛ߦⴕ߁⋧੕⚿ว✂ࠍኻ⽎  CP/MISF ᴺ 㧔 Critical Path/Most Immediateߣߔࠆ‫ߢߎߘޕ‬㧘એਅߩࠃ߁ߥಽᢔࡔࡕ࡝ဳࡑ࡞࠴ࡊࡠ

Successors First㧕࠮࠶ࠨࠍࡕ࠺࡞ൻߒߚ‫ޕ‬ฦࡊࡠ࠮࠶ࠨߪࡠ࡯ࠞ࡞ࡔࡕ࡝㧘%2/+5( ᴺߪࡅࡘ࡯࡝ࠬ࠹ࠖ࠶ࠢࠕ࡞ࠧ࡝࠭ࡓߢ޽ࠅ㧘౉಴ജㅢାࡃ࠶ࡈࠔ߇หߓ᭴ᚑߢ޽ࠆ‫ޕ‬࡮ ࡔࡕ࡝෸߮ㅢାࡃ࠶ࡈࠔߩኈ㊂ߪචಽ޽ࠆߣߔࠆ‫ޕ‬࡝ࠬ࠻ࠬࠤࠫࡘ࡯࡝ࡦࠣߦ߅޿ߡ࠲ࠬࠢߩఝవ㗅૏ࠍ⠨࡮ ࠺࡯࠲ߪ㕖หᦼߦㅍฃାߐࠇࠆ‫ޕ‬ㅍା஥ࡊࡠ࠮࠶ࠨᘦߔࠆ߽ߩߢ޽ࠆ‫ޕ‬ታⴕน⢻ߣߥߞߚ࠲ࠬࠢᢙ߇ࠕࠗ࠼ߪㅍା࠺࡯࠲ࠍㅢାࡃ࠶ࡈࠔߦᦠ߈ㄟߺ㧘ฃା஥ࡊ࡞ࡊࡠ࠮࠶ࠨᢙࠃࠅᄙ޿ߣ߈㧘ഀࠅᒰߡ࠲ࠬࠢߩㆬᛯߩࡠ࠮࠶ࠨߪฃା࠺࡯࠲ࠍㅢାࡃ࠶ࡈࠔ߆ࠄ⺒ߺㄟ߻‫ޕ‬ఝవᐲࠍ᳿ቯߔࠆߚ߼ߦᰴߩࠃ߁ߥ⚻㛎ೣࠍ↪޿ࠆ‫ޕ‬࡮ ㅍฃାਛࡊࡠ࠮࠶ࠨߪභ᦭ߐࠇߕ㧘࠺࡯࠲߇ㅍࠅర

Ԙ㧙㧙ฦ࠲ࠬࠢ߆ࠄ಴ญࡁ࡯࠼߹ߢߩᦨ㐳ࡄࠬ㐳ࠍ⸘▚‫ޕ‬ԙᦨ㐳ࡄࠬ㐳ߩ㒠㗅ߦࡊ࡜ࠗࠝ࡝࠹ࠖ࡝ࠬ࠻ࠍ૞ᚑ‫ޕ‬ߩࡅࡘ࡯࡝ࠬ࠹ࠖ࠶ࠢ⊛ߦ⦟޿⸃߇㓸߹ࠆߣផ᷹ߢ߈ࠆԚᦨ㐳ࡄࠬ㐳߇╬ߒߌࠇ߫㧘ߘߩਛߢ⋥ធᓟ⛯࠲ࠬࠢᏀ߆ࠄฝ߳㧘ᨑಾࠅࠍⴕ޿ߥ߇ࠄᷓߐఝవត⚝ࠍⴕ߁‫ޕ‬߹ߚ㧘DF/IHS ᴺߪᒝ NP ࿎㔍ߥࠢ࡜ࠬߦዻߔࠆ໧㗴ߩᄙ޿㗅ߦ㧘ࡊ࡜ࠗࠝ࡝࠹ࠖ࡝ࠬ࠻ࠍ૞ᚑ‫ޕ‬ԛవⴕ࠲ࠬࠢߩታⴕ߇⚳ࠊࠅ㧘ታⴕน⢻ߥ࠲ࠬࠢߩਛࠍోត⚝ߢ⸃᳿ߒࠃ߁ߣߔࠆߚ߼㧘࠲ࠬࠢࠣ࡜ࡈ߇ᢙච

ߢࡊ࡜ࠗࠝ࡝࠹ࠖ࡝ࠬ࠻ߩఝవᐲ߇㜞޿߽ߩ߆ࠄⓨ୘એ਄ߩ࠲ࠬࠢࠍᜬߟߣ⤘ᄢߥត⚝ᤨ㑆ࠍᔅⷐߣߔࠆ‫ޕ‬޿ߡ޿ࠆࡊࡠ࠮࠶ࠨߦഀࠅᒰߡࠆ‫ޕ‬ ᨑಾࠅ
㧔Depth First/Implicit Heuristic Search㧕 DF/IHS ᴺᨑಾࠅߣߪ㧘ࠬࠤࠫࡘ࡯࡞㐳ߩ⍴❗߇࿑ࠇߥ޿ㇱಽᧁ=?

ᴺ ߩត⚝ࠍᛂߜಾࠆᠲ૞ߢ޽ࠆ‫⃻ޕ‬࿷ߩࠬࠤࠫࡘ࡯࡞ㅜਛ ోត⚝ᚻᴺߣߒߡ᦭ലߥ⸃ᴺߦ DF/IHS ᴺ߇޽ࠆ‫ߎޕ‬⚿ᨐߣ㧘ߎࠇ߆ࠄᦨૐ߆߆ࠆಣℂᤨ㑆ߩว⸘㧔ታⴕน⢻ߎߢㅀߴࠆ DF/IHS ᴺߪࡊࡠ࠮࠶ࠨࠍᗧ࿑⊛ߦࠕࠗ࠼࡞࠲ࠬࠢએ㒠ߩᱷሽಣℂᤨ㑆ਅ㒢୯㧘એਅ㧘ߎࠇࠍනߦਅ⁁ᘒߦߔࠆߎߣ߽⠨ᘦߒߡ㧘ᦨㆡ⸃޽ࠆ޿ߪ♖ᐲߩ଻⸽㒢୯ߣ๭߱㧕߇੹߹ߢߦᓧࠄࠇߡ޿ࠆᦨ⦟ߩࠬࠤࠫࡘ࡯ߐ ࠇ ߚ ㄭ ૃ ⸃ ࠍ ᓧ ࠆ ߎ ߣ ߇ ߢ ߈ ࠆ ‫ ޕ‬DF/IHS ᴺ ߪ࡞㐳ࠃࠅᄢ߈ߊߥࠆߣᨑಾࠅࠍⴕ߁‫ޕ‬࿑  ߢߪ㧘ԙߩ

CP/MISF ᴺߦ߅ߌࠆࡅࡘ࡯࡝ࠬ࠹ࠖ࠶ࠢലᨐߣ㧘⚵ߺ႐วߦᨑಾࠅ߇⊒↢ߔࠆ‫ޕ‬วࠊߖᦨㆡൻ໧㗴ߦኻߒߡᦨ߽᦭ലߥಽᨑ㒢ቯᴺߣ๭߫ࠇࠆត⚝ᚻᴺࠍขࠅ౉ࠇߚត⚝ࠕ࡞ࠧ࡝࠭ࡓߢ޽ࠆ‫ޕ‬࿑  ߪ DF/IHS ᴺߢߩត⚝ⓨ㑆ߩ଀ߢ޽ࠆ‫ޕ‬ฦࡁ࡯⃻ᤨὐ䈪᳞䉁䈦䈩䈇䉎ᥳቯ⸃࠼ߪታⴕน⢻࠲ࠬࠢߩ߁ߜ㧘ࠕࠗ࠼࡞ࡊࡠ࠮࠶ࠨߦഀᒰ⃻ᤨὐ䉁䈪䉴䉬䉳䊠䊷䊦䈚䈢ᤨ㑆 ታⴕน⢻䉺䉴䉪䈱ਅ㒢୯㽲ߡࠆ࠲ࠬࠢ⇟ภߩ⚵วߖࠍ⴫ߔ߽ߩߢ޽ࠅ㧘Ǿߪࡊࡠ࠮࠶ࠨࠍࠕࠗ࠼࡞ߦߔࠆߎߣࠍᗧ๧ߒߡ޿ࠆ‫ޕ‬ห৻ߩᷓߐታⴕน⢻䉺䉴䉪䈱ਅ㒢୯㽳ߩត⚝ࡁ࡯࠼ߪ㧘ታⴕน⢻࠲ࠬࠢߩਛߢࡊ࡜ࠗࠝ࡝࠹ࠖ࡟ࡌ࡞ߩ㜞޿࠲ࠬࠢߩ⚵วߖߩ㗅ߦᏀ஥߆ࠄਗࠎߢ޿ࠆ‫ޕ‬ಽᨑ㒢ቯᴺߪ㧘ߎߩ᭽ߥត⚝ⓨ㑆ߩਛࠍᷓߐఝవត⚝ߒ࿑  ᨑಾࠅߦࠃࠆ㒢ቯᠲ૞ߡ޿߈㧘ߘߩᤨὐߢ᳞߹ߞߡ޿ࠆᥳቯ⸃ࠃࠅ߽ࠃ޿⸃߇ᓧࠄࠇࠆᲤߦ⸃ࠍᦝᣂߔࠆ‫৻ޕ‬ᣇߢ㧘ࠃ޿⸃߇ᓧࠄࠇߘᨑಾࠅߩಣℂߪએਅߩᚻ㗅ߢⴕࠊࠇࠆ‫ޕ‬߁ߦߥ޿ㇱಽᧁߪ㧘ߘߩ࠲ࠬࠢಣℂ㐿ᆎ߆ࠄᦨ⚳࠲ࠬࠢΣ ಣℂࠍⴕߞߚ࠲ࠬࠢߩਛߢಣℂ⚳ੌᤨೞ߇ᦨ߽ㆃ޿ᤨೞߣߥࠆ࠲ࠬࠢߩ⚳ੌᤨ㑆ࠍ᳞߼ࠆ‫ޕ‬ಣℂ⚳ੌ߹ߢᦨૐ㒢ᔅⷐߥಣℂᤨ㑆ߢ޽ࠆ࠲ࠬࠢߩਅ㒢୯ࠍ૶↪ߒ㧘ᣧ޿ᤨᦼߦᨑಾࠅߣ޿߁㒢ቯᠲ૞ࠍⴕߞߡΤ ಣℂࠍⴕߞߡ޿ߥ޿࠲ࠬࠢߩਅ㒢୯ߩਛߢᦨᄢߩਅ㒢୯ࠍ᳞߼ࠆ‫ޕ‬ή㚝ߥត⚝㊂ࠍ೥ᷫߒ㧘ᦨㆡ⸃ࠍ⷗ߟߌࠆᣇᴺߢ޽ࠆ‫ޕ‬Υ ΣߣΤߩว⸘୯ߣᥳቯ⸃ࠍᲧセߔࠆ‫ޕ‬
Ready
Task=[䋱䋬䋲䋬䋳䋬㱢]46 =㧝㧞㧟Ǿ?

䋰Φ ᥳቯ⸃ߩ୯ࠍ⿥߃ߚࠄ㧘ᨑಾࠅࠍⴕ߁‫ޕ‬

46 =㧟㧢Ǿ?
RT=[䋳䋬䋶䋬㱢]એ਄ߩᠲ૞ࠍⴕ߁ߎߣߢ㧘ή㚝ߥត⚝㊂ࠍ೥ᷫߔࠆ‫ޕ‬䋱䋬䋲䋱䋬䋳䋱䋬㱢䋲䋬䋳

RT=[4䋬㱢]46 =㧠Ǿ?

䋳䋬䋶䋳䋬㱢䋶䋬㱢䊶䊶䊶䊶䊶䊶

RT=[5䋬㱢]46 =㧡Ǿ?

䋴䋬㱢䋲䋬㱢䋳䋬㱢䊶䊶䊶㧠 ត⚝ⓨ㑆ߩ೥ᷫᴺࠬࠤࠫࡘ࡯࡝ࡦࠣߦ߅ߌࠆᐢᄢߥត⚝ⓨ㑆ߪ໧㗴ߢ޽

46 4GCF[6CUMߩ㓸ว
RT=[䋸䋬䋷䋬㱢]46 =㧤㧣Ǿ?

ࠆ‫߼ߚߩߘޕ‬㧘ዋߒߢ߽ࠬࠤࠫࡘ࡯࡝ࡦࠣߔࠆᔅⷐߩߥ䋵䋬㱢޿ត⚝ⓨ㑆ࠍಽᨆߒߡ೥ᷫࠍⴕ߁ߎߣ߇ᄢಾߢ޽ࠆ‫ߘޕ‬
RT=[㱢]46 =Ǿ?

䋸䋬䋷䋸䋬㱢䋷䋬㱢ߩߚ߼㧘ߔߢߦ㐿⊒ߐࠇߚត⚝ⓨ㑆ߩ೥ᷫᴺߢ޽ࠆ㧟㧿㱢䋷䋬㱢䋸䋬㱢

㧔Shrinking Search Space㧕ᴺߩਛߢ㧘ᦨㆡ⸃ࠍㅏߔߎߣߩߥ޿㧞ߟߩᚻᴺࠍขࠅ౉ࠇߡ޿ࠆ‫ޕ‬࿑  &(+*5 ᴺߦࠃࠆត⚝ᧁ

DF/IHS ᴺߢߪ㧘CP/MISF ᴺߩࡊ࡜ࠗࠝ࡝࠹ࠖ࡝ࠬ࠻

 ᔅⷐߥࠕࠗ࠼࡞࠲ࠬࠢߩ᛽಴ᴺ=?ࠍ૶↪ߔࠆߎߣߢ㧘࿑  ߩᦨᏀ┵ߩ⸃߇ CP/MISF ᴺࠕࠗ࠼࡞࠲ࠬࠢߣߪ㧘ࡊࡠ࠮࠶ࠨࠍᜰቯߒߚᤨ㑆ⓨ޿ߩ⸃ߣ╬ߒߊ㧘♖ᐲߩ㜞޿⸃୥⵬ߣߥࠆ‫ߚ߹ޕ‬㧘ត⚝ᧁߚ߹߹ߦߔࠆߚ߼ߩଢቱ਄ߩ࠲ࠬࠢߢ޽ࠅ㧘ᰴߩ࠲ࠬࠢ㧙㧙ߩഀࠅᒰߡࠍ᡿ᗧߦㆃࠄߖࠆߎߣߦࠃࠅ㧘ࠬࠤࠫࡘ࡯࡞Ԛฦࡊࡠ࠮࠶ࠨߪ࠲ࠬࠢࠣ࡜ࡈࠍోត⚝ߔࠆ㓙ߩត㐳ߩᡷༀࠍⴕ޿ߚ޿ᤨߦ↪޿ࠄࠇࠆ‫ߪࠢࠬ࠲࡞࠼ࠗࠕޕ‬⚝ᧁߩᖱႎࠍ଻᦭ߒߡ޿ߡ㧘master ߣ slave 㑆ߢㅢ޿ߟ߽ᔅⷐߛߣߪ㒢ࠄߥ޿ߚ߼㧘⸃ᨆน⢻ߢ޽ࠆਇᔅⷐାߐࠇࠆត⚝▸࿐ߩᖱႎߪߘߩត⚝ᧁߩᷓߐߣಽ

ߥࠕࠗ࠼࡞࠲ࠬࠢߩഀࠅᒰߡࠍⴕࠊߥ޿ᣇᴺߢ޽ࠆ‫ޕ‬ጘᢙߩߺߣߥࠆ‫ޕ‬slave ߪฃߌขߞߚᖱႎߩᷓߐߩಽጘࠃࠅవߩㇱಽᧁࠍត⚝ߔࠆߎߣߦߥࠆ‫ߦࠇߎޕ‬=?

 ࠲ࠬࠢഀࠅᒰߡ೙㒢ᴺ ࠃߞߡਗ೉ត⚝ߦ߅ߌࠆࠝ࡯ࡃࡋ࠶࠼ߣߥࠆㅢାㅢᏱ㧘ࠬࠤࠫࡘ࡯࡝ࡦࠣߢߪ࠲ࠬࠢࠍฦࡊࡠ࠮࠶ࠨߦ

㊂ࠍᛥ೙ߒߡ޿ࠆ‫ޕ‬ഀࠅᒰߡࠆ⚵ߺวࠊߖࠍ㧘㗅೉ࠍ↪޿ߡߔߴߡ↢ᚑߒߡ

Ready
Task=[䋱䋬䋲䋬䋳䋬㱢]46 =㧝㧞㧟Ǿ?

ࠬࠤࠫࡘ࡯࡝ࡦࠣࠍⴕߞߡ޿ࠆ‫ߒ߆ߒޕ‬㧘࠲ࠬࠢഀࠅᒰ䋰46 =㧟㧢Ǿ?
RT=[䋳䋬䋶䋬㱢]

ߡ೙㒢ᴺߢߪ㧘ߔߴߡߩഀࠅᒰߡߦߟ޿ߡ⠨ᘦߒߥߊߡ䋱䋬䋲䋱䋬䋳䋱䋬㱢䋲䋬䋳߽ᦨㆡ⸃߇ᓧࠄࠇ㧘ࠬࠤࠫࡘ࡯࡝ࡦࠣߦ߅ߌࠆត⚝▸࿐䋲䋬㱢䋳䋬㱢䊶䊶䊶

RT=[4䋬㱢]46 =㧠Ǿ?

ࠍዊߐߊߔࠆߎߣ߇಴᧪ࠆ‫ޕ‬䋳䋬䋶䋳䋬㱢䋶䋬㱢䊶䊶䊶䊶䊶䊶

RT=[5䋬㱢] 䋴䋬㱢
46 =㧡Ǿ?

46 4GCF[6CUMߩ㓸ว㧡 ࠬࠤࠫࡘ࡯࡝ࡦࠣ໧㗴ߩਗ೉ត⚝⸃ᴺ

RT=[䋸䋬䋷䋬㱢]46 =㧤㧣Ǿ?

䋵䋬㱢
RT=[㱢]46 =Ǿ?

ࠬࠤࠫࡘ࡯࡝ࡦࠣ໧㗴ߪ㧘ోត⚝ࠍⴕ߁ߣᒝ 02 ࿎㔍ߥ䋸䋬䋷䋸䋬㱢䋷䋬㱢㱢䋷䋬㱢䋸䋬㱢ࠢ࡜ࠬߦዻߔ⚵ߺวࠊߖᦨㆡൻ໧㗴ߢ޽ࠆߎߣ߇⍮ࠄࠇߡ޿ࠆ‫ߢߎߘޕ‬㧘೨ㅀߒߚត⚝ࠕ࡞ࠧ࡝࠭ࡓࠍਗ೉ൻߔ
ࠆ‫ޕ‬ਗ೉ൻߦࠃߞߡត⚝ⓨ㑆ߪⶄᢙߩࡊࡠ࠮࠶ࠨߦಽᢔ

䈖䈱૏⟎䉁䈪master䈏ត⚝䉕ⴕ䈦䈢ᤨὐ䈪slave䈎䉌ഀ䉍ᒰ䈩ⷐ᳞䈏⊒↢䈜䉎䈫䇮౞䈱ㇱಽ䈏slave䈮ኻ䈜䉎ഀ䉍ᒰ䈩▸࿐䈫䈭䉎䇯ߐࠇ㧘ᣧᦼߦ⦟޿⸃߇⊒⷗ߐࠇࠆߎߣߢᨑಾࠅߦࠃࠆ㒢ቯᠲ૞߇Ⴧടߒ㧘ή㚝ߥត⚝ߩ೥ᷫ߇น⢻ߦߥࠆ‫ߩߘޕ‬࿑ OCUVGT ߩ UNCXG ߦኻߔࠆត⚝▸࿐ߩഀࠅᒰߡߚ߼㧘ࠬࠤࠫࡘ࡯࡝ࡦࠣല₸߇ะ਄ߔࠆ‫ߒ߆ߒޕ‬㧘ត⚝ߦᔅⷐߥᖱႎߩ౒᦭ߦㅢାᤨ㑆߇߆߆ࠆน⢻ᕈ߇޽ࠆߚ㧢 ㅢାࠍ⠨ᘦߒߚਅ㒢୯߼㧘ㅢାߩ࠲ࠗࡒࡦࠣࠍ⠨ᘦߒ㧘ㅢା㊂ࠍᛥ߃ࠆᔅⷐ߇޽ࠆ‫੹ޕ‬࿁ⴕߞߚࠬࠤࠫࡘ࡯࡝ࡦࠣࡊࡠࠣ࡜ࡓߩਗ೉ൻ ࠲ࠬࠢࠬࠤࠫࡘ࡯࡝ࡦࠣߢߩᨑಾࠅᠲ૞ߣࡊ࡜ࠗࠝ࡝ߩᣇᴺࠍએਅߦ⸥ߔ‫ޕ‬࠹ࠖ࡟ࡌ࡞⸳ቯߦߪ㧘ฦ࠲ࠬࠢ߆ࠄ಴ญ࠲ࠬࠢ߹ߢߩᦨԘ ࡊࡠ࠮࠶ࠨߩਛߩ৻ߟࠍ master㧘ߘߩઁߩࡊࡠ࠮

࠶ࠨࠍ slave ߣ๭߱⇣ߥࠆត⚝ᣇᴺࠍⴕ߁㧞⒳㘃

⍴〒㔌ࠍ૶↪ߔࠆ‫ࠍࠇߎޕ‬ਅ㒢୯ߣ๭߱‫ޕ‬ᓥ᧪૶↪ߔࠆߦಽ㘃ߔࠆ‫ޕ‬ࠢ㑆ߩㅢାߦࠃࠆㆃᑧߪ⠨ᘦߐࠇߡ޿ߥ޿‫ޕ‬ฦ࠲ࠬࠢߩਅ㒢୯ߪฦ࠲ࠬࠢߩಣℂᤨ㑆ࠍరߦ▚಴ߒߡ޿ߡ㧘࠲ࠬ࡮ master ߩേ߈1.

2.

ਅ㒢୯ࠍ᳞߼ࠆ㓙ߦ࠲ࠬࠢ㑆ߩㅢାࠍ⠨ᘦߔࠆߣ㧘ਅ㒢ㅙᰴࠬࠤࠫࡘ࡯࡝ࡦࠣߣหߓᣇᴺߢត⚝‫ޕ‬slave ߆ࠄត⚝ⓨ㑆ߩⷐ᳞߇޽ࠆߣ㧘ⷐ᳞ࠍฃ୯⸘▚߇ಣℂࡊࡠ࠮࠶ࠨ㧘࠲ࠬࠢ㧘ㅢାߩ⚵ߺวࠊߖࠍߌขߞߚᤨὐߢ⥄ࠄ߇ࠬࠤࠫࡘ࡯࡝ࡦࠣߒߚߊߩᤨ㑆ࠍ⾌߿ߒߡߒ߹߁‫ޕ‬⠨߃ࠆ⚵ߺวࠊߖᦨㆡൻ໧㗴ߣߥࠅ㧘ਅ㒢୯ߩ▚಴ߦᄙࡊࡠ࠮࠶ࠨ㧘࠲ࠬࠢ㧘ㅢାߩ⚵ߺวࠊߖએ㒠ᨑಾࠅ߿ࡊ࡜ࠗࠝ࡝࠹ࠖ࡟ࡌ࡞ߦ૶↪ߒ㧘ࠬࠤࠫࡘ࡯࡝ⓨ㑆ࠍഀࠅᒰߡࠆ ࿑  ‫ޕ‬࡮ slave ߩേ߈ࡦࠣᕈ⢻ࠍะ਄ߔࠆߎߣࠍ⋡ᮡߣߒߡ޿ࠆ‫ߪߢߎߎޕ‬ਅ

2.

ߩ▚಴ᣇᴺࠍ⺑᣿ߔࠆ‫ޕ‬1.

⥄ࠄ߇ត⚝ࠍⴕ߁ត⚝▸࿐ࠍ master ߦⷐ᳞‫ޕ‬㒢୯⸘▚ߦ᧦ઙࠍട߃ࠆߎߣߢ⸘▚ᤨ㑆ࠍᛥ߃ߚਅ㒢୯ฃߌขߞߚត⚝▸࿐ߩត⚝ࠍⴕ޿㧘⚳ੌว࿑߇ߊࠆ߹ߢត⚝▸࿐ࠍⷐ᳞ߒ⛯ߌࠆ‫ޕ‬ԙᧄ⎇ⓥߢߪ㧘ㅢାࠍ⠨ᘦߒߚ࠲ࠬࠢߩਅ㒢୯ࠍ᳞߼ߡߩ⚵ߺวࠊߖߩࠬࠤࠫࡘ࡯࡝ࡦࠣࠍⴕ߁ត⚝master ߣ slave ߪಣℂ㐿ᆎᤨೞ㧘࠲ࠬࠢ㧘ࡊࡠ࠮࠶ ਅ㒢୯⸘▚ߩ᧦ઙࠨ㧘ㅢାߩ⚵ߺวࠊߖࠍ  ߟㆬᛯߔࠆߚ߮ߦઁߩࡊࠄ಴ญ࠲ࠬࠢ߹ߢߩᦨ⍴⚻〝ࠍ᳞߼ࠆᔅⷐ߇޽ࠆ‫߆ߒޕ‬ ਅ㒢୯⸘▚ߢߪ㧘ਅ㒢୯ࠍ᳞߼ࠆ࠲ࠬࠢ߇⚳ੌߒߡ߆ࡠ࠮࠶ࠨ߆ࠄߩᦝᣂߐࠇߚᥳቯ⸃ߩㅢାߩ᦭ήࠍߒ㧘ᓟ⛯࠲ࠬࠢߩߔߴߡߩㅢା⁁ᴫࠍ⠨ᘦߔࠆߎߣߪ࿎⏕⹺ߔࠆ‫޿⦟ߡߞࠃߦࠇߎޕ‬ᥳቯ⸃ࠍᣧᦼߦ⷗ߟߌ㔍ߢ޽ࠆ‫߼ߚߩߘޕ‬㧘ਅ㒢୯ߩ⸘▚߇ⶄ㔀ൻߒߥ޿ࠃ߁ߡᨑಾࠅࠍⴕ޿㧘ή㚝ߥត⚝ࠍ೥ᷫߔࠆ‫ޕ‬ߥએਅߩ᧦ઙࠍ⸳ቯߒߚ‫ޕ‬㧙㧙Ԙ ⋥ធᓟ⛯࠲ࠬࠢߩਅ㒢୯ࠍరߦ⸘▚ߔࠆ‫ޕ‬ԙ ߔߴߡߩಣℂⵝ⟎ߪࠕࠗ࠼࡞⁁ᘒߣߔࠆ‫ޕ‬䉺䉴䉪A䉺䉴䉪䋱䉺䉴䉪䋲䉺䉴䉪tԚ ಣℂⵝ⟎ߩᢙࠍ೙㒢ߒߥ޿‫ޕ‬ԛ ᓟ⛯࠲ࠬࠢห჻ߩవⴕ㑐ଥࠍ⠨ᘦߒߥ޿‫ޕ‬࿑ 0%2' ߦ߅ߌࠆ࠲ࠬࠢߩಣℂ૏⟎ߎࠇߦࠃࠅ⌀ߩᦨ⍴⚻〝ߣߪ޿߆ߥ޿߇㧘ᓥ᧪ߦᲧߴߡ♖ᐲߩ㜞޿ਅ㒢୯߇න⚐ߥ⸘▚ߢ▚಴ߢ߈ࠆ‫ޕ‬߹ߚ㧘࠲ࠬࠢ A ߩ⋥ធᓟ⛯࠲ࠬࠢࠍ NCPE ߦഀࠅᒰ
 ਅ㒢୯⸘▚ਅ㒢୯ߣߪ㧘ਅ㒢୯ࠍ᳞߼ߚ޿࠲ࠬࠢߩಣℂᓟ߆ࠄ಴ญ࠲ࠬࠢಣℂ߹ߢߩᦨૐ㒢ᔅⷐߥಣℂᤨ㑆ࠍ᳞߼㧘ߘߩߡߚᤨ㧘⥄りߩ pass ߇⛘ኻࡄࠬ㐳ߣߥࠆ࠲ࠬࠢࠍx㧘xએ೨ߦಣℂߔࠆ࠲ࠬࠢࠍw㧘xએᓟߦಣℂߔࠆ࠲ࠬࠢࠍy ߣ๭߱‫ޕ‬୯ߣਅ㒢୯ࠍ᳞߼ߚ޿࠲ࠬࠢߩಣℂᤨ㑆ࠍว▚ߒߚ୯ߢ䉺䉴䉪A 䊶䊶䊶޽ࠆ‫ޕ‬䉺䉴䉪w 䊶䊶䊶䉺䉴䉪x䊶䊶䊶䉺䉴䉪yਅ㒢୯⸘▚ߢ૶↪ߔࠆ୯ࠍએਅߦ⸥ߔ‫ޕ‬Aਅ㒢୯ࠍ᳞߼ࠆ࠲ࠬࠢ

NCPE( Non Communication Processor Element )࿑ ࠲ࠬࠢ Y㧘Z㧘[ ߩ૏⟎㑐ଥ࠲ࠬࠢ A ࠍಣℂߒߚࡊࡠ࠮࠶ࠨ

࠲ࠬࠢ A ಣℂᓟߩ⛘ኻࡄࠬ㐳ߪ࠲ࠬࠢ A ࠍಣℂߒߡ޿ߥ޿ࡊࡠ࠮࠶ࠨߣ޿߁ᑼߢ᳞߼ࠄࠇࠆ‫߈ߣߩߎޕ‬㧘࠲ࠬࠢ x ࠍᓟᣇߢಣCPE( Communication Processor Element )tછᗧߩ⋥ធᓟ⛯࠲ࠬࠢtime(t)࠲ࠬࠢ t ߩಣℂᤨ㑆com(t)࠲ࠬࠢ A ߆ࠄ࠲ࠬࠢ t ߳ߩㅢାᤨ㑆
lb(t)࠲ࠬࠢ t ߩਅ㒢୯lb’(t)lb(t) - time(t)

pass(x)= time(1)+…+time(x)+lb’(x)ℂߔࠆߣ time(1)㨪time(x)߇Ⴧടߔࠆߎߣߦߥࠆߩߢ

Ԙ࠲ࠬࠢ x ࠍߘߩ૏⟎ࠃࠅᓟᣇߢಣℂߔࠆߣ⛘ኻࡄࠬ㐳ߪჇടߔࠆ‫ޕ‬ԙ߹ߚ㧘એਅߩ㧞ߟߩᑼࠃࠅw ߣ y ߩಣℂ㗅ࠍ౉ࠇ឵߃ࠆߣ⛘ኻࡄࠬ㐳ߪჇടߔࠆ‫ޕ‬pass(t)࠲ࠬࠢ A ಣℂᓟ࠲ࠬࠢ t ࠍㅢࠆ಴ญ࠲ࠬࠢ߹

pass(w)=time(1)+…+time(x)+…+time(y)+lb’(w)lb’(w) > lb’(x)ߢߦᔅⷐߥಣℂᤨ㑆⛘ኻࡄࠬ㐳࠲ࠬࠢ A ߩ⋥ធᓟ⛯࠲ࠬࠢߩࡊࡠ࠮࠶ࠨԚ߹ߚ㧘࠲ࠬࠢ x ߩಣℂࠍ೨ᣇߢಣℂߔࠆߣరߩ࠲ࠬࠢx ߩ㗅ߢಣℂߔࠆ࠲ࠬࠢ w ߇↢ߓࠆߩߢ㧘࠲ࠬࠢ x ࠍߦኻߔࠆഀࠅᒰߡᣇߏߣߩ⋥ធᓟ⛯࠲ࠬࠢߩ pass ߩᦨᄢ୯NCPE ߣ CPE ߩ㆑޿ߪ࠲ࠬࠢ A ߩಣℂߦ޽ࠆ‫ࠬ࠲ޕ‬ࠢ A ࠍಣℂߒߚࡊࡠ࠮࠶ࠨߪ࠲ࠬࠢ A ߩ⋥ធᓟ⛯࠲ࠬߘߩ૏⟎ࠃࠅ೨ᣇߢಣℂߔࠆߣ⛘ኻࡄࠬ㐳ߪჇടߔࠆ‫ޕ‬pass(w)=time(1)+…+time(x)+lb’(w) lb’(x) > lb’(x)Ԙ㧘ԙ㧘Ԛࠃࠅ NCPE ߦ߅޿ߡ lb’ߩ㒠㗅ߦ࠲ࠬࠢࠍࠢࠍಣℂߒߡ߽ㅢାߪᔅⷐߥ޿‫ߩߡోࠄߥߗߥޕ‬ᔅⷐߥ࠺࡯࠲ߪࡠ࡯ࠞ࡞ߦሽ࿷ߔࠆ߆ࠄߢ޽ࠆ‫߼ߚߩߘޕ‬㧘

ಣℂߔࠆߣ⛘ኻࡄࠬ㐳߇ᦨዊߣߥࠆ‫ޕ‬

NCPE ߣ๭ࠎߢ޿ࠆ‫ ࠢࠬ࠲ޕ‬A ࠍಣℂߒߡ޿ߥ޿ࡊࡠ࠮ ోߡߩࡊࡠ࠮࠶ࠨࠍ૶↪ߔࠆ႐ว

ࠬࠢ A ࠍಣℂߒߚࡊࡠ࠮࠶ࠨ߆ࠄᔅⷐߥ࠺࡯࠲ࠍฃߌߩᦨૐ㒢ᔅⷐߥಣℂᤨ㑆ࠍ᳞߼ࠆ‫ޕ‬CPE ߢ࠲ࠬࠢ t ࠍಣ࠶ࠨߢߪ࠲ࠬࠢ A ߩ⋥ធᓟ⛯࠲ࠬࠢࠍಣℂߔࠆ႐ว㧘࠲ขࠄߥߌࠇ߫ߥࠄߕ㧘ࡊࡠ࠮࠶ࠨ㑆ߦㅢାᤨ㑆߇⊒↢ߔࠆ‫߼ߚߩߘޕ‬㧘CPE ߣ๭ࠎߢ޿ࠆ‫ޕ‬ NCPE ߢోߡߩ࠲ࠬࠢࠍಣℂߔࠆ႐วᰴߦ CPE ߽૶↪ߒߡಣℂߔࠆ႐วߩ࠲ࠬࠢ A ⚳ੌᓟ

ℂߔࠆߣ࠲ࠬࠢ t ߩࡄࠬߪ com(t)+lb(t)ߣߥࠆ‫ޕ‬ߘߩߚ߼㧘એਅߩᚻ㗅ߢ࠲ࠬࠢ A ⚳ੌᓟߩᦨૐ㒢ᔅⷐߥಣℂᤨ㑆ࠍ᳞߼ࠆ‫ޕ‬߹ߕ㧘NCPE ߦߔߴߡߩ⋥ធᓟ⛯࠲ࠬࠢࠍഀࠅᒰߡࠆ

Ԙ NCPE ߢಣℂߒߡ޿ࠆ࠲ࠬࠢߩਛߢ com(t)+lb(t)߇

ಣℂᤨ㑆ߪ㧘lb’ߩ㒠㗅ߦ࠲ࠬࠢࠍಣℂߒߚᤨߩ⛘ኻࡄࠬࠕ NCPE ߢಣℂߔࠆ࠲ࠬࠢ t ߇㧝ߟߥࠄ㧘ߘߩ႐วࠍ⠨߃ࠆ‫ᤨߩߎޕ‬㧘࠲ࠬࠢ A ⚳ੌᓟߩᦨૐ㒢ᔅⷐߥᦨዊߣߥࠆ࠲ࠬࠢ t ࠍត⚝ߔࠆ ࿑  ‫ޕ‬࠲ࠬࠢߩࡄࠬ߇᳞߼ࠆ୯ߣߥࠆ‫ޕ‬㐳ߣߥࠆ‫⸽ࠍࠇߘߪߢߎߎޕ‬᣿ߔࠆ‫ޕ‬

NCPE ߢోߡߩ࠲ࠬࠢ߇ಣℂߐࠇࠆ႐ว㧘࠲ࠬࠢ t ߪlb’߇㒠㗅ߩ⁁ᘒߢ࠲ࠬࠢ A ߩಣℂᓟ t ⇟⋡ߦಣℂߔࠆ࠲ࠬࠢߣߔࠆ‫ޕ‬㧙㧙㒢୯ࠍࡊ࡜ࠗࠝ࡝࠹ࠖ࡟ࡌ࡞ߣߒߡ૶↪ߔࠆߎߣߦߒߚ‫ޕ‬

䉺䉴䉪A䉺䉴䉪t㧣 ታⴕߣ⹏ଔ࿑ ࠲ࠬࠢ t ߩㆬᛯ⹏ଔᣇᴺߣታⴕⅣႺࠬࠤࠫࡘ࡯࡝ࡦࠣല₸ߩ⹏ଔߪ  ⒳㘃ⴕߞߚ‫ޕ‬ԙ NCPE ߢಣℂߔࠆ࠲ࠬࠢߩ pass ߩਛߢᦨᄢߣߥࠆ ߟ⋡ߩ⹏ଔߪ  ⒳㘃ߩਅ㒢୯ࠍ↪޿ߡ⹏ଔ↪࠲ࠬࠢ୯ࠍត⚝ߔࠆ‫ޕ‬ࠣ࡜ࡈࠍోត⚝ߒ㧘ᦨㆡ⸃ࠍ᳞߼ࠆ㓙ߩត⚝ᤨ㑆ࠍᲧセԚ ԙߩ୯ߣ com(t)+lb(t)ࠍᲧセߔࠆ‫ޕ‬ߒߚ㧔એਅ㧘ត⚝ᤨ㑆⹏ଔߣ๭߱㧕‫ޕ‬ᓥ᧪ߩਅ㒢୯ࠃࠅㅢࠕ com(t)+lb(t)߇ᄢ߈޿ߥࠄԙߩ୯߇᳞߼ࠆ୯‫ޕ‬
ࠗ com(t)+lb(t)߇ዊߐ޿ߥࠄ㧘࠲ࠬࠢ t ࠍ CPEߢಣℂߔࠆ ࿑  ‫ޕ‬ାࠍ⠨ᘦߒߚਅ㒢୯ࠍ૶↪ߒߚᣇ߇㧘ోត⚝ᤨ㑆߇ߤߩߊࠄ޿೥ᷫߐࠇࠆ߆ߢࠬࠤࠫࡘ࡯࡝ࡦࠣല₸ߩะ਄ࠍ⹏ଔߔࠆ‫ޕ‬ ߟ⋡ߩ⹏ଔߪ  ⒳㘃ߩਅ㒢୯ࠍ↪޿ߡ⹏ଔ↪࠲ࠬࠢ䉺䉴䉪A䉺䉴䉪tࠣ࡜ࡈߩࠬࠤࠫࡘ࡯࡝ࡦࠣࠍⴕ޿㧘⸳ቯߒߚᤨ㑆ߢ᳞߹ࠆᥳቯ⸃ࠍᲧセߒߚ㧔એਅ㧘ᥳቯ⸃⹏ଔߣ๭߱㧕‫⹏ߩߎޕ‬

䉺䉴䉪tଔߢߪ㧘ㅢାࠍ⠨ᘦߒߚਅ㒢୯ࠍ૶↪ߒߚ㓙ߩታ↪⊛ߥᤨ㑆ౝߢోត⚝ߢ߈ߥ޿ࠃ߁ߥ࠲ࠬࠢࠣ࡜ࡈߦኻߔࠆࠬ࿑ ࠲ࠬࠢ t ࠍಣℂߔࠆࡊࡠ࠮࠶ࠨߩㆬᛯࠤࠫࡘ࡯࡝ࡦࠣല₸ߩᄌൻࠍ⹏ଔߔࠆ⁓޿߇޽ࠆ‫ޕ‬ᓥ᧪ߩਅ㒢୯ࠃࠅㅢାࠍ⠨ᘦߒߚਅ㒢୯ࠍ૶↪ߒߚᣇ߇㧘⸳ԛ NCPE ߢಣℂߔࠆ࠲ࠬࠢ߆ࠄ࠲ࠬࠢ t ࠍ㒰޿ߡ㧘

NCPE ߢಣℂߔࠆ࠲ࠬࠢߩ pass ߩᦨᄢ୯ࠍ᳞߼ࠆቯߒߚᤨ㑆ߢ᳞߹ࠆᥳቯ⸃߇ߤߩߊࠄ޿⍴❗ߔࠆ߆ߢࠬࠤࠫࡘ࡯࡝ࡦࠣല₸ߩะ਄ࠍ⹏ଔߔࠆ‫ޕ‬૶↪ߒߚࡑࠪࡦߩ઀᭽ߪએਅߢ޽ࠆ‫ޕ‬CPU : Intel(R) Xeon(R) X5550 @ 2.67GHz x 2࿑  ‫ޕ‬OS : LinuxRAM : 12GB䉺䉴䉪Aߎࠇࠄ  ߟߩ⹏ଔߪਗ೉ត⚝ߦ߅ߌࠆ⋧ਸ਼ലᨐ߽ᦼᓙ䉺䉴䉪tߢ߈ࠆߚ߼㧘਄⸥ߩࡑࠪࡦߢ㧤ࠦࠕࠍ૶↪ߒߡਗ೉ត⚝ࠍⴕߞߚ‫ޕ‬࿑ ࠲ࠬࠢ t ࠍ 0%2' ߆ࠄ೥㒰 ត⚝ᤨ㑆⹏ଔត⚝ᤨ㑆⹏ଔ↪࠲ࠬࠢࠣ࡜ࡈ࡮ ᧄ⎇ⓥቶߩ࡜ࡦ࠳ࡓ࠲ࠬࠢࠣ࡜ࡈࠫࠚࡀ࡟࡯࠲ߢ↢Ԝ ԛߩ୯ߣ com(t)+lb(t)ࠍᲧセ‫ޕ‬ࠕ com(t)+lb(t)߇ᄢ߈޿ߥࠄ com(t)+lb(t)߇᳞߼
ࠆ୯‫ޕ‬

ࠗ com(t)+lb(t)߇ዊߐ޿ߥࠄԘߦᚯࠆ‫ޕ‬એ਄Ԙ㨪ԛߩᚻ㗅ߢ᳞߼ߚ୯ߦ࠲ࠬࠢ A ߩಣℂᤨ㑆ࠍട߃ߚ୯߇࠲ࠬࠢ A ߩਅ㒢୯ߣߥࠆ‫ޕ‬ᚑߒߚ࠲ࠬࠢࠣ࡜ࡈ࡮ ࠲ࠬࠢᢙ ࡮ ࠲ࠬࠢಣℂᤨ㑆 㨪࡮ ㅢାᤨ㑆Ԙ㨪ԙ㨪Ԛ㨪࡮ ᓟ⛯࠲ࠬࠢᢙ 㨪వⴕ࠲ࠬࠢᢙ 㨪࡮ ࠲ࠬࠢࠣ࡜ࡈ  ୘ߩㅢାᤨ㑆ࠍ  Ბ㓏⸳ቯߒߡ㧘ว ਅ㒢୯ߩ૶↪ᣇᴺ⸘  ୘ߩ࠲ࠬࠢࠣ࡜ࡈࠍ↢ᚑ‫ޕ‬ត⚝ᤨ㑆⹏ଔᣇᴺ ᳞߼ߚਅ㒢୯ߪᦨ⍴⚻〝ߩㄭૃ୯ߣߒߡ♖ᐲ߇਄߇ߞᓥ᧪ߩਅ㒢୯ࠍ૶↪ߒߡ࠲ࠬࠢࠣ࡜ࡈߩ  ࡊࡠ࠮࠶ࠨߡ޿ࠆߚ߼㧘ᨑಾࠅߦ૶↪ߔࠆ‫ߒ߆ߒޕ‬㧘ࡊ࡜ࠗࠝ࡝࠹ߦኻߔࠆࠬࠤࠫࡘ࡯࡝ࡦࠣࠍⴕ߁‫ߩߘޕ‬ᓟ㧘੹࿁ឭ᩺ߔࠖ࡟ࡌ࡞ߣߒߡ૶↪ߔࠆߎߣߪࡅࡘ࡯࡝ࠬ࠹ࠖ࠶ࠢ⊛ߢࠆㅢାࠍ⠨ᘦߒߚਅ㒢୯ࠍ૶↪ߒߡត⚝ᤨ㑆⹏ଔ↪࠲ࠬ޽ࠆߚ߼㧘ᓥ᧪ߩਅ㒢୯ࠃࠅត⚝ല₸߇ᔅߕ⦟ߊߥࠆߣࠢࠣ࡜ࡈߩ  ࡊࡠ࠮࠶ࠨߦኻߔࠆࠬࠤࠫࡘ࡯࡝ࡦࠣࠍⴕߪ㒢ࠄߥ޿‫ߢߎߘޕ‬㧘㧞⒳㘃ߩਅ㒢୯ࠍࡊ࡜ࠗࠝ࡝࠹ࠖ߁‫ޕ‬એ਄㧞ߟߩࠬࠤࠫࡘ࡯࡝ࡦࠣߢߩត⚝ᤨ㑆ࠍᲧセߒ࡟ࡌ࡞ߣߒߡ૶↪ߒߚត⚝ߢߩೋᦼ⸃߇⦟޿⸃ߣߥࠆਅߡ㧘੹࿁ឭ᩺ߔࠆㅢାࠍ⠨ᘦߒߚਅ㒢୯ࠍ૶↪ߒߚ႐ว㧙㧙ߩࠬࠤࠫࡘ࡯࡝ࡦࠣല₸ߩะ਄ࠍ⹏ଔߔࠆ‫ޕ‬ࠆ‫ోޕ‬૕ᐔဋߢߪត⚝ᤨ㑆߇ ೥ᷫߐࠇߡ޿ࠆ‫ޕ‬ ᥳቯ⸃⹏ଔㅢା䉕⠨ᘦ䈚䈢ਅ㒢୯䈮䉋䉎ត⚝ᤨ㑆೥ᷫ₸ᥳቯ⸃⹏ଔ↪࠲ࠬࠢࠣ࡜ࡈ㪈㪇㪇㩼࡮ ᣧⒷ↰ᄢቇ═ේ⎇ⓥቶߩᮡḰ࠲ࠬࠢ࠮࠶࠻=?ត⚝ᤨ㑆೥ᷫ₸㪏㪇㩼࡮ ࠲ࠬࠢᢙ ࡮ CCR ߣ๭߫ࠇࠆᲧࠍ↪޿ߡㅢାᤨ㑆ࠍઃടߒߚ‫ޕ‬㧔CCRㅢାᤨ㑆ߩ✚๺࠲ࠬࠢಣℂᤨ㑆✚๺㧕=?࡮ ࠲ࠬࠢࠣ࡜ࡈ  ୘ߦ CCR ߩ୯ࠍ 㧘㧘 ߣ  Ბ㪍㪇㩼㪋㪇㩼㪉㪇㩼㪇㩼㪈 㪊 㪌 㪎 㪐 㪈㪈 㪈㪊 㪈㪌 㪈㪎 㪈㪐 㪉㪈 㪉㪊 㪉㪌 㪉㪎 㪉㪐 㪊㪈 㪊㪊 㪊㪌 㪊㪎 㪊㪐 㪋㪈 㪋㪊 㪋㪌 㪋㪎 㪋㪐 㪌㪈 㪌㪊 㪌㪌 㪌㪎 㪌㪐 㪍㪈 㪍㪊 㪍㪌 㪍㪎 㪍㪐 㪎㪈 㪎㪊 㪎㪌 㪎㪎 㪎㪐㪄㪉㪇㩼㪄㪋㪇㩼䉺䉴䉪䉫䊤䊐⇟ภ㓏⸳ቯߒߡ㧘ว⸘  ୘ߩ࠲ࠬࠢࠣ࡜ࡈࠍ↢ᚑ‫ޕ‬࿑ ㅢାࠍ⠨ᘦߒߚਅ㒢୯ߦࠃࠆត⚝ᤨ㑆೥ᷫ₸   ត⚝ᤨ㑆⹏ଔ ㅢାᤨ㑆 㨪 ߩ࠲ࠬࠢࠣ࡜ࡈ ⚿ᨐᥳቯ⸃⹏ଔᣇᴺᓥ᧪ߩਅ㒢୯ࠍ૶↪ߒߡ࠲ࠬࠢࠣ࡜ࡈߩ 4 ࡊࡠ࠮࠶ࠨ

ߦኻߔࠆࠬࠤࠫࡘ࡯࡝ࡦࠣࠍ 60 ⑽ߩត⚝ᤨ㑆ߢⴕ߁‫ߘޕ‬߶ߣࠎߤߩ࠲ࠬࠢࠣ࡜ࡈߦ߅޿ߡ㧘ត⚝ᤨ㑆ߩ೥ᷫ₸ߩᓟߢ੹࿁ឭ᩺ߔࠆㅢାࠍ⠨ᘦߒߚਅ㒢୯ࠍ૶↪ߒߡᥳ߇ࡊ࡜ࠬ஥ߦ಴ߡ޿ࠆ‫ࠅ߹ߟޕ‬㧘ㅢାࠍ⠨ᘦߒߚਅ㒢୯ቯ⸃⹏ଔ↪࠲ࠬࠢࠣ࡜ࡈߩ 4 ࡊࡠ࠮࠶ࠨߦኻߔࠆࠬࠤࠫࠍ૶↪ߔࠆߎߣߢត⚝ᤨ㑆ߪ೥ᷫߐࠇߡ޿ࠆߎߣ߇ࠊ߆

ࡘ࡯࡝ࡦࠣࠍ 60 ⑽ߩត⚝ᤨ㑆ߢⴕ߁‫ޕ‬એ਄㧞ߟߩࠬࠤࠫࠆ‫ోޕ‬૕ᐔဋߢߪត⚝ᤨ㑆߇ ೥ᷫߐࠇߡ޿ࠆ‫ޕ‬ࡘ࡯࡝ࡦࠣߢ᳞߹ߞߚ⸃ࠍᲧセߒߡ㧘੹࿁ឭ᩺ߔࠆㅢାㅢା䉕⠨ᘦ䈚䈢ਅ㒢୯䈮䉋䉎ត⚝ᤨ㑆೥ᷫ₸ࠍ⠨ᘦߒߚਅ㒢୯ࠍ૶↪ߒߚ႐วߩࠬࠤࠫࡘ࡯࡝ࡦࠣല㪈㪇㪇㩼₸ߩะ਄ࠍ⹏ଔߔࠆ‫ޕ‬ត⚝ᤨ㑆೥ᷫ₸㪏㪇㩼 ታⴕ⚿ᨐត⚝ᤨ㑆⹏ଔߩታⴕ⚿ᨐ㪍㪇㩼㪋㪇㩼㪉㪇㩼㪇㩼㪈 㪊 㪌 㪎 㪐 㪈㪈 㪈㪊 㪈㪌 㪈㪎 㪈㪐 㪉㪈 㪉㪊 㪉㪌 㪉㪎 㪉㪐 㪊㪈 㪊㪊 㪊㪌 㪊㪎 㪊㪐 㪋㪈 㪋㪊 㪋㪌 㪋㪎 㪋㪐 㪌㪈 㪌㪊 㪌㪌 㪌㪎 㪌㪐 㪍㪈 㪍㪊 㪍㪌 㪍㪎 㪍㪐 㪎㪈 㪎㪊 㪎㪌 㪎㪎 㪎㪐㪄㪉㪇㩼࿑ 㧘࿑ 㧘࿑  ߪᮮゲ߇࠲ࠬࠢࠣ࡜ࡈ⇟ภ㧘❑㪄㪋㪇㩼㪄㪍㪇㩼ゲ߇ត⚝ᤨ㑆೥ᷫ₸ߣߥߞߡ޿ࠆ‫ޕ‬(1) ត⚝ᤨ㑆⹏ଔ ㅢାᤨ㑆 㨪 ߩ࠲ࠬࠢࠣ࡜ࡈ ⚿ᨐ䉺䉴䉪䉫䊤䊐⇟ภ࿑ ㅢାࠍ⠨ᘦߒߚਅ㒢୯ߦࠃࠆត⚝ᤨ㑆೥ᷫ₸  ߶ߣࠎߤߩ࠲ࠬࠢࠣ࡜ࡈߦ߅޿ߡ㧘ត⚝ᤨ㑆ߩ೥ᷫ₸߇ࡊ࡜ࠬ஥ߦ಴ߡ޿ࠆ‫ࠅ߹ߟޕ‬㧘ㅢାࠍ⠨ᘦߒߚਅ㒢୯ᥳቯ⸃⹏ଔߩታⴕ⚿ᨐࠍ૶↪ߔࠆߎߣߢត⚝ᤨ㑆ߪ೥ᷫߐࠇߡ޿ࠆߎߣ߇ࠊ߆࿑ 㧘࿑ 㧘࿑  ߪᮮゲ߇࠲ࠬࠢࠣ࡜ࡈ⇟ภ㧘❑ࠆ‫ోޕ‬૕ᐔဋߢߪត⚝ᤨ㑆߇ ೥ᷫߐࠇߡ޿ߡ㧘ゲ߇ᥳቯ⸃ߩ⍴❗₸ߣߥߞߡ޿ࠆ‫ޕ‬એ਄ត⚝ᤨ㑆߇೥ᷫߐࠇߡ޿ࠆ࠲ࠬࠢࠣ࡜ࡈ߽ሽ࿷ߒߚ‫ޕ‬(1)ᥳቯ⸃⹏ଔ %%4 ߩ࠲ࠬࠢࠣ࡜ࡈ ߩ⚿ᨐ߶ߣࠎߤߩ࠲ࠬࠢࠣ࡜ࡈߦ߅޿ߡ㧘⸃ߩᡷༀ₸߇ࡊ࡜ࠬ஥ߦ಴ߡ޿ࠆ‫ࠅ߹ߟޕ‬㧘ㅢାࠍ⠨ᘦߒߚਅ㒢୯ࠍ૶↪

ㅢା䉕⠨ᘦ䈚䈢ਅ㒢୯䈮䉋䉎ត⚝ᤨ㑆೥ᷫ₸㪈㪇㪇㩼ߔࠆߎߣߢ⸃ߪᡷༀߐࠇߡ޿ࠆߎߣ߇ࠊ߆ࠆ‫ోޕ‬૕ᐔဋត⚝ᤨ㑆೥ᷫ₸㪏㪇㩼ߢߪ ᳞߹ࠆ⸃߇ᡷༀߒߚ‫ޕ‬㪍㪇㩼㪋㪇㩼ㅢା䉕⠨ᘦ䈚䈢ਅ㒢୯䈮䉋䉎⸃䈱ᡷༀ₸㪉㪇㩼㪇㩼㪎㩼㪈 㪊 㪌 㪎 㪐 㪈㪈 㪈㪊 㪈㪌 㪈㪎 㪈㪐 㪉㪈 㪉㪊 㪉㪌 㪉㪎 㪉㪐 㪊㪈 㪊㪊 㪊㪌 㪊㪎 㪊㪐 㪋㪈 㪋㪊 㪋㪌 㪋㪎 㪋㪐 㪌㪈 㪌㪊 㪌㪌 㪌㪎 㪌㪐 㪍㪈 㪍㪊 㪍㪌 㪍㪎 㪍㪐 㪎㪈 㪎㪊 㪎㪌 㪎㪎 㪎㪐㪍㩼㪄㪉㪇㩼䉺䉴䉪䉫䊤䊐⇟ภ࿑ ㅢାࠍ⠨ᘦߒߚਅ㒢୯ߦࠃࠆត⚝ᤨ㑆೥ᷫ₸  ⸃䈱ᡷༀ₸㪌㩼㪄㪋㪇㩼㪋㩼㪊㩼㪉㩼㪈㩼㪇㩼㪄㪈㩼㪈 㪉 㪊 㪋 㪌 㪍 㪎 㪏 㪐 㪈㪇 㪈㪈 㪈㪉 㪈㪊 㪈㪋 㪈㪌 㪈㪍 㪈㪎 㪈㪏 㪈㪐 㪉㪇 㪉㪈 㪉㪉 㪉㪊 㪉㪋 㪉㪌 㪉㪍 㪉㪎 㪉㪏 㪉㪐 㪊㪇㪄㪉㩼㪄㪊㩼 ត⚝ᤨ㑆⹏ଔ ㅢାᤨ㑆 㨪 ߩ࠲ࠬࠢࠣ࡜ࡈ ⚿ᨐ㪄㪋㩼䉺䉴䉪䉫䊤䊐⇟ภ߶ߣࠎߤߩ࠲ࠬࠢࠣ࡜ࡈߦ߅޿ߡ㧘ត⚝ᤨ㑆ߩ೥ᷫ₸߇ࡊ࡜ࠬ஥ߦ಴ߡ޿ࠆ‫ࠅ߹ߟޕ‬㧘ㅢାࠍ⠨ᘦߒߚਅ㒢୯࿑ ㅢାࠍ⠨ᘦߒߚਅ㒢୯ߦࠃࠆ⸃ߩ⍴❗₸  ࠍ૶↪ߔࠆߎߣߢត⚝ᤨ㑆ߪ೥ᷫߐࠇߡ޿ࠆߎߣ߇ࠊ߆㧙㧙 ᥳቯ⸃⹏ଔ(CCR=5 ߩ࠲ࠬࠢࠣ࡜ࡈ)ߩ⚿ᨐ߇⦟޿⸃ߢ޽ࠆਅ㒢୯ࠍࡊ࡜ࠗࠝ࡝࠹ࠖ࡟ࡌ࡞ߣߒߡ૶߶ߣࠎߤߩ࠲ࠬࠢࠣ࡜ࡈߦ߅޿ߡ㧘⸃ߩᡷༀ₸߇ࡊ࡜↪ߒߚߎߣ߇ේ࿃ߛߣᕁࠊࠇࠆ‫ߩߎޕ‬ᣇᴺߢㅢାࠍ⠨ᘦࠬ஥ߦ಴ߡ޿ࠆ‫ࠅ߹ߟޕ‬㧘ㅢାࠍ⠨ᘦߒߚਅ㒢୯ࠍ૶↪

ߒߚਅ㒢୯߇ࡊ࡜ࠗࠝ࡝࠹ࠖ࡟ࡌ࡞ߣߒߡ૶↪ߐࠇࠆߣ㧘ߔࠆߎߣߢ⸃ߪᡷༀߐࠇߡ޿ࠆߎߣ߇ࠊ߆ࠆ‫ోޕ‬૕ᐔဋᓥ᧪ߩਅ㒢୯ࠍ૶↪ߔࠆ႐วࠃࠅೋᦼ⸃ߪ⦟ߊߥࠆ߇㧘ߢߪ ᳞߹ࠆ⸃߇ᡷༀߒߚ‫ޕ‬ᥳቯ⸃߿ᦨㆡ⸃߇వߦ⷗ߟ߆ࠆ଻㓚ߪߥ޿‫߼ߚߩߘޕ‬㧘ᓥ᧪ߩਅ㒢୯ࠍ૶↪ߒߚ႐วࠃࠅត⚝ᤨ㑆߇ᑧ߮ߡߒ߹ߞߚߣ੍᷹ߒߡ޿ࠆ‫ޕ‬ㅢା䉕⠨ᘦ䈚䈢ਅ㒢୯䈮䉋䉎⸃䈱ᡷༀ₸ᥳቯ⸃⹏ଔߣ⠨ኤ㪈㪇㩼⸃ߩᡷༀ߇⷗ࠄࠇࠆ࠲ࠬࠢࠣ࡜ࡈߪ㒢ࠄࠇߡ޿ࠆ߇㧘⸃䈱ᡷༀ₸㪏㩼㪍㩼഍⊛ߦᖡߊߥࠆ଀ߪ⒘ߢ޽ࠅ㧘ㅢାࠍ⠨ᘦߒߚਅ㒢୯ߩ㪋㩼૶↪ߦࠃߞߡ⸃ߩᡷༀ௑ะ߇⷗ࠄࠇߚ‫ߩ⸃ޕ‬ᡷༀ௑ะ߇㪉㩼㪇㩼⷗ࠄࠇߚℂ↱ߣߒߡ㧘ㅢାࠍ⠨ᘦߒߚਅ㒢୯ࠍ૶↪ߔࠆ㪈 㪉 㪊 㪋 㪌 㪍 㪎 㪏 㪐 㪈㪇 㪈㪈 㪈㪉 㪈㪊 㪈㪋 㪈㪌 㪈㪍 㪈㪎 㪈㪏 㪈㪐 㪉㪇 㪉㪈 㪉㪉 㪉㪊 㪉㪋 㪉㪌 㪉㪍 㪉㪎 㪉㪏 㪉㪐 㪊㪇㪄㪉㩼ߎߣߢ㧘⦟޿⸃ߩᣧᦼ⊒⷗ߣᨑಾࠅߦࠃࠆត⚝ⓨ㑆೥ᷫ㪄㪋㩼㪄㪍㩼ߩჇടߦߟߥ߇ߞߚߎߣ߇ේ࿃ߣ੍᷹ߢ߈ࠆ‫ߚ߹ޕ‬㧘ㅢ䉺䉴䉪䉫䊤䊐⇟ภାࠍ⠨ᘦߒߚਅ㒢୯ߦࠃߞߡᄢ߈ߥࠬࠤࠫࡘ࡯࡝ࡦࠣല࿑ ㅢାࠍ⠨ᘦߒߚਅ㒢୯ߦࠃࠆ⸃ߩ⍴❗₸  ₸ะ਄ߩലᨐ߇಴ߥ߆ߞߚℂ↱ߦߪ㧘♖ᐲߩ㜞޿ਅ㒢୯ࠍ⸘▚ߢ߈ߚߣߒߡ߽㧘ᔅߕᣧᦼߦ⦟޿⸃߇⊒⷗ߢ߈ࠆ ᥳቯ⸃⹏ଔ CCR=10 ߩ࠲ࠬࠢࠣ࡜ࡈ ߩ⚿ᨐߣߪ㒢ࠄߥ޿ߣ޿ߞߚߎߣ߇᜼ߍࠄࠇࠆ‫੹ޕ‬࿁ߩࠬࠤࠫ߶ߣࠎߤߩ࠲ࠬࠢࠣ࡜ࡈߦ߅޿ߡ㧘⸃ߩᡷༀ₸߇ࡊ࡜ࡘ࡯࡝ࡦࠣࠕ࡞ࠧ࡝࠭ࡓߢߪ㧘ਅ㒢୯ࠍరߦࡅࡘ࡯࡝ࠬࠬ஥ߦ಴ߡ޿ࠆ‫ࠅ߹ߟޕ‬㧘ㅢାࠍ⠨ᘦߒߚਅ㒢୯ࠍ૶↪

࠹ࠖ࠶ࠢ⊛ߦ⦟޿⸃߇޽ࠆߣᕁࠊࠇࠆ㗅ߦត⚝ⓨ㑆ࠍតߔࠆߎߣߢ⸃ߪᡷༀߐࠇߡ޿ࠆߎߣ߇ࠊ߆ࠆ‫ోޕ‬૕ᐔဋ⚝ߔࠆ߇㧘ታ㓙ߦ⦟޿⸃߇ត⚝ⓨ㑆ߩߤߎߦሽ࿷ߒߡ޿ߢߪ ᳞߹ࠆ⸃߇ᡷༀߒߚ‫ޕ‬ࠆ߆ߪਇ᣿ߢ޽ࠆ‫߼ߚߩߘޕ‬㧘⦟޿⸃ߩᣧᦼ⊒⷗ߣᨑಾࠅߦࠃࠆត⚝ⓨ㑆ߩ೥ᷫߩലᨐ߇ዋߥߊߥߞߚน⢻ᕈ߇⠨߃ࠄࠇࠆ‫ޕ‬ㅢା䉕⠨ᘦ䈚䈢ਅ㒢୯䈮䉋䉎⸃䈱ᡷༀ₸ో૕ߩ⹏ଔߣ⠨ኤ㪊㪌㩼ᦨㆡ⸃ࠍ᳞߼ࠄࠇࠆోត⚝ߢߩ⹏ଔߢߪ㧘೙㒢ᤨ㑆ౝ⸃䈱ᡷༀ₸㪊㪇㩼㪉㪌㩼ߢⴕ߁ᥳቯ⸃⹏ଔࠃࠅត⚝ᤨ㑆߇㐳ߊ㧘ត⚝▸࿐߇ᄢ߈㪉㪇㩼㪈㪌㩼߆ߞߚߚ߼㧘⦟޿⸃ߩᣧᦼ⊒⷗ߩലᨐߣᨑಾࠅߦࠃࠆត㪈㪇㩼㪌㩼⚝ⓨ㑆೥ᷫߩലᨐ߇ᄢ߈ߊ㧘ࠬࠤࠫࡘ࡯࡝ࡦࠣല₸ߩะ㪇㩼㪄㪌㩼㪈 㪉 㪊 㪋 㪌 㪍 㪎 㪏 㪐 㪈㪇 㪈㪈 㪈㪉 㪈㪊 㪈㪋 㪈㪌 㪈㪍 㪈㪎 㪈㪏 㪈㪐 㪉㪇 㪉㪈 㪉㪉 㪉㪊 㪉㪋 㪉㪌 㪉㪍 㪉㪎 㪉㪏 㪉㪐 㪊㪇਄ߦኻߔࠆലᨐ߇ᄢ߈߆ߞߚߣᕁࠊࠇࠆ‫ߚ߹ޕ‬㧘ᦨㆡ⸃㪄㪈㪇㩼㪄㪈㪌㩼ࠍ᳞߼ࠆߎߣ߇಴᧪ߥ޿ᥳቯ⸃ߩ⹏ଔߢߪ㧘ត⚝ᤨ㑆ߣ䉺䉴䉪䉫䊤䊐⇟ภត⚝▸࿐߇㒢ቯߐࠇࠆߎߣߢ㧘⦟޿⸃ߩᣧᦼ⊒⷗ߩലᨐ࿑ ㅢାࠍ⠨ᘦߒߚਅ㒢୯ߦࠃࠆ⸃ߩ⍴❗₸  ߣᨑಾࠅߦࠃࠆត⚝ⓨ㑆೥ᷫߩჇട߇ᛥ߃ࠄࠇߡߒ߹޿㧘ࠬࠤࠫࡘ࡯࡝ࡦࠣല₸ߩะ਄ߦኻߔࠆലᨐ߇ዋߥߊߥߞ ⹏ ଔߚߣ⠨߃ࠄࠇࠆ‫ోޕ‬૕⊛ߦߪ㧘ࠬࠤࠫࡘ࡯࡝ࡦࠣല₸ะត⚝ᤨ㑆⹏ଔߣ⠨ኤ਄ߩ᏷߇࠲ࠬࠢࠣ࡜ࡈߦଐሽߒߡ޿ࠆ߇㧘⹏ଔߢߪ᳿߼ో૕ࠍㅢߒߡ 㨪ㄭ޿ត⚝ᤨ㑆߇೥ᷫߐࠇߡ޿ࠆ‫ޕ‬ࠄࠇߚᤨ㑆ౝߢߩᥳቯ⸃߇⍴❗௑ะߦ޽ࠅ㧘ోត⚝ᤨ㑆ߎࠇߪ♖ᐲߩ㜞޿ਅ㒢୯ࠍ૶↪ߔࠆߎߣߢ㧘⦟޿⸃ߩᣧߪᷫዋ௑ะߦ޽ࠆ‫ࠅ߹ߟޕ‬㧘♖ᐲߩ㜞޿ਅ㒢୯ࠍ૶↪ߔᦼ⊒⷗ߣᨑಾࠅߦࠃࠆត⚝ⓨ㑆೥ᷫߩჇടߦߟߥ߇ߞߚࠆߎߣߢ㧘⦟޿⸃ߩᣧᦼ⊒⷗ߣᨑಾࠅߦࠃࠆត⚝ⓨ㑆೥ߎߣ߇ේ࿃ߣ੍᷹ߢ߈ࠆ‫ߚ߹ޕ‬㧘ត⚝ᤨ㑆ߩ೥ᷫ₸߇࠲ᷫߩჇടߦߟߥ߇ࠅ㧘ࠬࠤࠫࡘ࡯࡝ࡦࠣല₸߇ะ਄ߒߚࠬࠢࠣ࡜ࡈߦଐሽߒߡ޿ߚ‫ߪࠇߎޕ‬㧘ㅢାࠍ⠨ᘦߒߡਅߣ⠨߃ࠄࠇࠆ‫ޕ‬㒢୯ࠍ⸘▚ߔࠆߎߣߢߩਅ㒢୯♖ᐲߩะ਄₸߇࠲ࠬࠢࠣ࡜ࡈߏߣߦ⇣ߥࠆߎߣ߇ේ࿃ߢ޽ࠆߣᕁࠊࠇࠆ‫ߚ߹ޕ‬㧘৻ㇱߩ࠲ࠬࠢࠣ࡜ࡈߢ೥ᷫ₸߇ࡑࠗ࠽ࠬߦߥߞߡ޿ߚ‫ޕ‬ߎࠇߪࡊ࡜ࠗࠝ࡝࠹ࠖ࡟ࡌ࡞ߣߒߡ૶↪ߒߚ㓙ߩೋᦼ⸃㧙㧙㧤 ⚳ࠊࠅߦ࠲ࠬࠢࠣ࡜ࡈߦߪ࠲ࠬࠢಣℂᤨ㑆㧘ㅢାᤨ㑆㧘వⴕ࠲ࠬࠢ㧘ᓟ⛯࠲ࠬࠢߥߤߦߘࠇߙࠇ⇣ߥߞߚ․ᓽ߇޽ࠆ‫ޕ‬ߘߩߚ߼㧘ࠬࠤࠫࡘ࡯࡝ࡦࠣ໧㗴ߢߪోߡߩ࠲ࠬࠢࠣ࡜ࡈߦ߅ߌࠆห᭽ߥࠬࠤࠫࡘ࡯࡝ࡦࠣല₸ߩะ਄ߪ㔍ߒ޿߇㧘੹࿁ឭ᩺ߒߚㅢାࠍ⠨ᘦߒߚਅ㒢୯ࠍ૶↪ߒߚ㒢ቯᠲ૞ߢߩࠬࠤࠫࡘ࡯࡝ࡦࠣߢߪ㧘ࠬࠤࠫࡘ࡯࡝ࡦࠣല₸ߩะ਄௑ะ߇⏕⹺ߢ߈ߚ‫ޕ‬੹࿁ߪਅ㒢୯ត⚝ߦᤨ㑆ࠍ߆ߌߥ޿ࠃ߁ߦߔࠆߚ߼ߦⶄᢙߩ᧦ઙࠍ⸳ߌߚ‫᧦ߩߎޕ‬ઙࠍዋߥߊߔࠆߎߣߢߐࠄߦ♖ᐲߩ㜞޿ਅ㒢୯߇૞ᚑน⢻ߢ޽ࠆ‫ߚ߹ޕ‬㧘഍⊛ߥࠬࠤࠫࡘ࡯࡝ࡦࠣല₸ߩะ਄ߦߪᣂߚߥត⚝ࠕ࡞ࠧ࡝࠭ࡓߩ⠨᩺߇ᔅ㗇ߢ޽ࠆߣ⠨߃ߡ޿ࠆ‫ޕ‬⻢ ㄉᧄ⎇ⓥߩ৻ㇱߪ㧘ᢥㇱ⑼ቇ⋭ᚢ⇛⊛⎇ⓥၮ⋚ᒻᚑᡰេ੐ᬺߩ⵬ഥࠍฃߌߡⴕߞߚߎߣࠍߎߎߦ⸥ߒ㧘⻢ㄉࠍ⴫ߒ߹ߔ‫ޕ‬ෳ⠨ᢥ₂[1] ═ේඳᓼ‫ޟ‬ਗ೉ಣℂᛛⴚ‫␠࠽ࡠࠦޠ‬1991[2] ᵤ↰⠹ᴦ㧘‫ޟ‬ㅢାࠍ⠨ᘦߒߚ࠲ࠬࠢࠬࠤࠫࡘ࡯࡝ࡦࠣ໧㗴ߩត⚝⸃ᴺ‫ޠ‬ᚑくᄢቇᄢቇ㒮Ꮏቇ⎇ⓥ⑼ᖱႎಣ
ℂኾ᡹ୃ჻⺰ᢥ2004[3] STG(Standard Task Graph Set),

http://www.kasahara.elec.waseda.ac.jp/schedule/index.html

2010 ᐕ 1 ᦬[4] O.Sinnen, “Task Scheduling for Parallel Systems”,

Wiley-Interscience (2007)㧙㧙