動的タイム・ボローイングを可能にするクロッキング方式の適用手法の評価

全文

(1)Vol.2013-ARC-206 No.6 2013/7/31. ৘ใॲཧֶձ‫ڀݚ‬ใࠂ IPSJ SIG Technical Report. ಈతλΠϜɾϘϩʔΠϯάΛՄೳʹ͢Δ ΫϩοΩϯάํࣜͷద༻ख๏ͷධՁ ٢ా फ࢙1,a). ޿ാ ૖Ұ࿠1. ૔ా ੒‫ݾ‬1. ‫ޒ‬ౡ ਖ਼༟1. ࡔҪ मҰ1. ֓ཁɿ൒ಋମϓϩηεͷඍࡉԽʹ൐͏ճ࿏஗Ԇͷ͹Β͖ͭͷ૿Ճ͕, ճ࿏ઃ‫͚͓ʹܭ‬Δେ͖ͳ໰୊ͱͳΓͭ ͭ͋Δ. ͹Β͖͕ͭ૿େ͍ͯ͘͠ͱ, ैདྷͷϫʔετɾέʔεʹ‫͍ͨͮج‬ઃ‫ܭ‬ख๏͸൵‫؍‬తʹͳΓ͗͢Δ. ͦͷͨΊ, ϫʔετɾέʔεΑΓ࣮ࡍʹ͍ۙ஗Ԇʹ‫͍ͨͮج‬ಈ࡞Λ࣮‫͢ݱ‬Δख๏͕ఏҊ͞Ε͍ͯΔ. զʑ͸ Ҏલɼಈతͳ͹Β͖ͭରࡦख๏ͱͯ͠ͷλΠϛϯάɾϑΥʔϧτ‫ݕ‬ग़Λ, ೋ૬ϥονͷΫϩοΩϯάํࣜʹ ૊Έ߹ΘͤΔ͜ͱʹΑ࣮ͬͯ‫͞ݱ‬ΕΔ, ಈతλΠϜɾϘϩʔΠϯάΛՄೳʹ͢ΔΫϩοΩϯάํࣜΛఏҊ͠ ͨɽຊख๏ʹΑͬͯ, ಈ࡞࣌ʹεςʔδؒͰճ࿏஗ԆΛ༥௨͠, ࣮ޮ஗Ԇʹ͍ۙ଎౓Ͱಈ࡞ͤ͞Δ͜ͱ͕Մ ೳʹͳΔ. ຊߘͰ͸, ͜ͷํࣜͷద༻ΛࣗಈͰߦ͏πʔϧͷߏ੒๏΍ΞϧΰϦζϜʹ͍ͭͯड़΂Δɽ. 1. ͸͡Ίʹ ൒ಋମϓϩηεͷඍࡉԽʹ൐͍ɼૉࢠͷϥϯμϜͳ͹Β. ͜Εʹର͠ Razor Ͱ͸ɼϫʔετɾέʔεΑΓ΋௿͍ి ѹ (V)ɼߴ͍प೾਺ (F) Ͱಈ࡞ͤ͞ɼͦͷ݁Ռੜ͡Δ TF Λ‫ݕ‬ग़/ճ෮͢Δɽճ෮ʹ͸ϖφϧςΟ͕෇ਵ͢Δ͔Βɼͦ. ͖ͭͷ໰୊͕‫ࡏݦ‬Խͭͭ͋͠Δ [1], [2]ɽඍࡉԽʹΑͬͯɼ. ͷӨ‫े͕ڹ‬෼ʹখ͘͞ͳΔΑ͏ʹɼTF ͷൃੜ֬཰͕े෼. ૉࢠੑೳͷฏ‫( ۉ‬typical) ஋͸޲্͢Δ΋ͷͷɼ͹Β͖ͭͷ. ʹ௿͍ V/F ͷ૊Λ‫͚ͭݟ‬Δɽ͜ͷΑ͏ʹ͢Ε͹ɼϫʔε. ૿େʹΑͬͯϫʔετ஋ͷ޲্͸‫͞ࡴݮ‬ΕΔɽैདྷͷ LSI. τɾέʔεઃ‫Ͱܭ‬ඞཁͰ͋ͬͨϚʔδϯΛ࡟‫͢ݮ‬Δ͜ͱ͕. ઃ‫ܭ‬͸ɼ͜ͷϫʔετ஋ʹ‫ͮ͘ج‬ϫʔετɾέʔεઃ‫Ͱܭ‬. Ͱ͖ɼ൵‫؍‬తա͗Δ‫ੵݟ‬΋Γ͔Β୤٫͢Δ͜ͱ͕Ͱ͖Δɽ. ͋Δɽ͕ͨͬͯ͠ɼ͜ͷ··ඍࡉԽΛਐΊͯ΋ैલͷΑ͏. Ҏલ·ͰͷఏҊ. ͳੑೳ޲্͸‫ظ‬଴Ͱ͖ͳ͘ͳΔɽ ಈతλΠϛϯάɾϑΥʔϧτ‫ݕ‬ग़ɾճ෮. զʑ͸Ҏલɼೖྗ͹Β͖ͭʹண໨͢Δ͜ͱʹΑΓ TF ‫ݕ‬ ग़ٕज़Λߋʹਪ͠ਐΊɼRazor Ͱ͸੒͠ಘͳ͔ͬͨɼΫϦ. λΠϛϯάɾϑΥʔϧτ (Timing Fault: TF) ͱ͸ɼճ. ςΟΧϧɾύεΑΓ͸Δ͔ʹ୹͍࣮ޮ஗Ԇʹ‫ͮ͘ج‬αΠΫ. ࿏஗ԆͷಈతͳมಈʹΑͬͯੜ͡Δա౉‫ނ‬োͰ͋Δɽ͜ͷ. ϧɾλΠϜΛ‫ن‬ఆͰ͖ΔΫϩοΩϯάํࣜΛఏҊ͍ͯ͠. TF Λ‫ݕ‬ग़͠ɼճ෮͢Δ͜ͱʹΑΓɼϫʔετɾέʔεઃ. Δ [7]ɽ࣮ޮ஗Ԇ͸ϩδοΫͷग़ྗ͕࠷ऴతʹ֬ఆͨ͠஗. ‫͔ܭ‬Βͷ୤٫ΛਤΔٕज़͕ఏҊ͞Ε͍ͯΔɽ͜ͷΑ͏ͳ. Ԇ࣌ؒΛද͢ɽೖྗ͹Β͖ͭͱ࣮ޮ஗Ԇͷৄ͍͠ఆٛ͸. ٕज़ͱͯ͠ɼRazor [3], [4], [5] ͕༗໊Ͱ͋ΓɼDVFS -. 2.1 અͰड़΂Δɽ. Dynamic Voltage and Frequency Scaling [6] ͱ૊Έ߹Θͤ ͯ༻͍ΒΕΔɽ ϫʔετɾέʔεઃ‫Ͱܭ‬͸૝ఆͨ͠ಈ࡞৚݅಺ͷϫʔε. ఏҊํࣜ͸ɼ୺తʹ‫͑ݴ‬͹ɼTF ‫ݕ‬ग़ͱೋ૬ϥονΛ૊ Έ߹Θͤͨ΋ͷͰɼ͜ͷ͜ͱʹΑΓಈతλΠϜɾϘϩʔΠ ϯά͕ՄೳʹͳΔɽ3.1 અͰৄ͘͠ड़΂Δ͕ɼैདྷ͔Β͋. τɾέʔεͷ஗ԆΛ‫ੵݟ‬΋Γɼͦͷ৔߹Ͱ΋ TF ͕ൃੜ͠. Δೋ૬ϥονํࣜͰՄೳʹͳΔλΠϜɾϘϩʔΠϯά͸ɼ. ͳ͍Α͏ʹిѹ (V) ͱप೾਺ (F) ͷ૊Λઃఆ͢Δɽͨ͠. ‫ݴ‬Θ͹੩తλΠϜɾϘϩʔΠϯάͱ‫΂ݺ‬Δ΋ͷͰɼઃ‫࣌ܭ‬. ͕ͬͯɼ࣮ࡍʹ TF ͕‫͜ى‬Δͷ͸ɼαʔϞɾηϯαͷ‫ނ‬ো. ʹεςʔδؒͰ஗ԆΛ༥௨͢Δ΋ͷͰ͋ΔɽಈతλΠϜɾ. ʹΑΔ೤๫૸ͳͲͷ૝ఆ֎ͷঢ়‫͍͓ͯʹگ‬ͷΈͰ͋ΔɽҰ. ϘϩʔΠϯάͱ͸ɼ࣮ߦ࣌ʹ࣮ޮ஗Ԇ͕αΠΫϧɾλΠϜ. ํͰɼϫʔετɾέʔεʹ͓͍ͯ΋ TF ͕ൃੜ͠ͳ͍Α͏. Ҏ্ʹ৳ͼͯ͠·ͬͨ৔߹ɼ͜ͷ௒ա෼Λ࣍ͷεςʔδʹ. ͳ‫ੵݟ‬΋Γ͸ɼ͹Β͖͕ͭ૿େͨ͠ϓϩηεͰ͸൵‫؍‬తʹ. ࣋ͪӽ͢ͱ͍͏΋ͷͰ͋Δɽ࣍ͷεςʔδͷ࣮ޮ஗Ԇ͕୹. ͳΓա͗Δɽ. ͚Ε͹ɼ͜ͷ௒ա෼͸૬ࡴ͞ΕΔɽ͜ͷ͜ͱʹΑΓ࣮ޮ஗. 1. Ԇͷ෼ࢄΛ‫ٵ‬ऩ͠ɼ࣮ޮ஗Ԇͷฏ‫͍ۙʹۉ‬αΠΫϧɾλΠ. a). ౦‫ژ‬େֶ େֶӃ ৘ใཧ޻ֶ‫ڀݚܥ‬Պ Graduate School of Information Science and Technology, The University of Tokyo [email protected]. c 2013 Information Processing Society of Japan . ϜͰͷಈ࡞͕ՄೳͱͳΔͷͰ͋Δɽ ·ͨɼಈతλΠϜɾϘϩʔΠϯάΛߦͬͯ΋ɼαΠΫϧɾ. 1.

(2) Vol.2013-ARC-206 No.6 2013/7/31. ৘ใॲཧֶձ‫ڀݚ‬ใࠂ IPSJ SIG Technical Report. λΠϜ͸࣮ޮ஗Ԇͷ෼෍ʹैͬͯແ੍‫୹ʹݶ‬ॖͰ͖ΔΘ͚. ͷ೾‫ܗ‬Λฒ΂ͳ͚Ε͹ͳΒͳ͍ɽͦΕʹରͯ͠ t-diagram. Ͱ͸ͳ͍ɽTF Λ‫ݕ‬ग़͢Δख๏ʹ͸ɼ͜ΕҎ্࡟‫͢ݮ‬Δͱ. ͸ɼԼํ޲͕࣌ؒΛɼӈํ޲͕ճ࿏தΛ৴߸͕఻Θͬͯߦ. TF ͕ਖ਼͘͠‫ݕ‬ग़Ͱ͖ͳ͘ͳΔ‫ݕ‬ग़‫ݶ‬ք͕ଘࡏ͢ΔɽRazor. ͘ํ޲Λද͠ɼ࣌ؒͷ‫ܦ‬աʹͭΕͯ৴߸͕఻Θ͍༷ͬͯ͘. ͷ‫ݕ‬ग़‫ݶ‬ք͸ɼΫϦςΟΧϧɾύε஗Ԇͷ 2/3 ഒఔ౓Ͱ͋. ࢠΛ၆ᛌ͢Δ͜ͱ͕Ͱ͖Δɽ. ΔɽఏҊख๏Ͱ͸ߋʹɼTF ͷ‫ݕ‬ग़ํ๏Λ޻෉͢Δ͜ͱʹ. ਤ 1ʢ্ʣʹࣔ͢ճ࿏Ͱɼ࣌ࠁ t = 0 ʹ 3 ͭͷ FF ͷग़ྗ. ΑΓɼ͜ͷ‫ݕ‬ग़‫ݶ‬քΛΫϦςΟΧϧɾύε஗Ԇͷ 1/2 ഒ΁. (x, y, z) ͕ (1, 1, 0) ͔Β (0, 0, 1) ʹભҠͨ͠ͱ͢Δɽxɼy ɼ. ͱ࡟‫͢ݮ‬Δ͜ͱ͕Ͱ͖Δɽ. z ͔Β d ʹࢸΔύεͷ஗ԆΛͦΕͧΕ tx ɼty ɼtz ͱ͢Δͱɼ. ఏҊख๏͸ɼओʹ͜ΕΒ 2 ఺ʹΑΓɼαΠΫϧɾλΠϜ. ϩδοΫͷग़ྗ d ͸ɼ࣌ࠁ t = tx ɼty ʹ͓͍ͯ 0 → 1 → 0. 1/2ɼ͢ͳΘͪɼಈ࡞प೾਺ 2 ഒΛୡ੒͢Δ͜ͱ͕Ͱ͖Δɽ. ͱભҠ͢Δɽz ͔Β d ʹࢸΔύε্Λ఻ΘΔ৴߸͸ɼy ͔. ຊߘͷ಺༰. Β d ʹࢸΔύεͷ৴߸ʹΑͬͯϚεΫ͞ΕΔͨΊɼ࣌ࠁ. จ‫[ ݙ‬7] Ͱ͸ɼൺֱత؆୯ͳճ࿏ʹରͯ͠ख࡞‫Ͱۀ‬ఏҊ. t = tz ʹ͸ग़ྗ͸มԽ͠ͳ͍͜ͱʹ஫ҙ͞Ε͍ͨɽಉਤͷ. ํࣜΛద༻͠ɼFPGA ্ͰఏҊํ͕࣮ࣜࡍʹಈ࡞प೾਺. ӈ୺ʹ͋Δ೾‫͕ܗ‬ɼd ʹ͓͚Δ௨ৗͷλΠϜɾνϟʔτʢΛ. 2 ഒͰಈ࡞͢Δ͜ͱΛ֬ೝ͍ͯ͠Δɽ͔͠͠ɼϓϩηοα. ӈʹ 90◦ ճసͨ͠΋ͷʣͰ͋Δɽ. ͷΑ͏ʹճ࿏‫ن‬໛͕େ͖͍΋ͷʹର͢Δద༻Λख࡞‫ߦͰۀ‬. ύεͷ‫׆‬ੑԽͱλΠϛϯάɾμΠΞάϥϜ. ͏ͷ͸ɼෆՄೳʹ͍ۙɽ. ಉਤͷΑ͏ʹ t-diagram Ͱ͸ɼϩδοΫͷೖྗʹ͓͍ͯ. ͦ͜Ͱ‫ࡏݱ‬ɼ൚༻ͷճ࿏Λάϥϑߏ଄ʹམͱ͠ࠐΈɼఏ. ೖྗ͕มԽͨ࣌͠ࠁ͔ΒɼಉϩδοΫͷग़ྗʹ͓͍ͯग़ྗ. Ҋํࣜͷద༻ΛࣗಈͰߦ͏πʔϧͷ։ൃΛਐΊ͍ͯΔɽຊ. ͕มԽͨ࣌͠ࠁ·ͰΛ௚ઢ໼ҹͰ݁Ϳ͜ͱʹΑͬͯɼ৴߸. ߘͰ͸͜ͷద༻ࣗಈԽπʔϧΛߏ੒͢Δࡍʹຬͨ͢΂͖ཁ. ͷ఻ΘΔ༷ࢠΛද͢ɽ. ݅Λྻ‫͠ڍ‬ɼ࣮ࡍͷΞϧΰϦζϜΛड़΂Δɽ. ਤ 1 ʹࣔͨ͠ྫͰ͸ɼલड़ͨ͠Α͏ʹɼz ͔Β d ʹࢸΔ. ҎԼɼ2 ষͰ͸·ͣɼҎલ·ͰͷఏҊΛࢧ͑Δೖྗ͹Βͭ. ύεΛ௨Δ৴߸͸్தͰϚεΫ͞ΕΔͨΊɼ࣌ࠁ t = tz ʹ. ͖ͱ࣮ޮ஗Ԇͷਖ਼֬ͳఆٛʹ͍ͭͯɼλΠϛϯάɾμΠΞ. ͓͍ͯ͸ग़ྗ d ͸มԽ͠ͳ͍ɽύεΛ௨ͬͨ৴߸ʹΑͬͯ. άϥϜͱ‫Ϳݺ‬ਤΛ‫ʹج‬આ໌͠ɼ͞Βʹ༷ʑͳ‫ط‬ଘͷΫϩο. ࣮ࡍʹϩδοΫͷग़ྗ͕มԽͨ͠ͱ͖ɼͦͷ৴߸ʹΑͬͯ. Ωϯάํࣜʹ͍ͭͯड़΂Δɽଓ͘ 3 ষͰɼҎલ·ͰͷఏҊ. ͦͷύε͕‫׆‬ੑԽͨ͠ͱ‫͏ݴ‬ɽ. ͷ֓ཁΛड़΂ɼ4 ষͰɼద༻ࣗಈԽπʔϧͷ࢓༷ͱߏ੒ʹ ͍ͭͯड़΂Δɽ. t-diagram Ͱ͸ɼύεΛ‫׆‬ੑԽͨ͠৴߸ͷ఻ୡΛ࣮ઢ໼ ҹͰද͢ɽ‫׆‬ੑԽ͠ͳ͔ͬͨ৔߹ʹ͸ɼ్தͰϚεΫ͞Ε. 2. ೖྗ͹Β͖ͭͱ‫ط‬ଘͷΫϩοΩϯάํࣜ ͲͷΑ͏ͳΫϩοΫΛ෼഑͢Δ͔ɼϑϦοϓɾϑϩοϓ. G T. [ . G. T. \ . G. T. ] . (FF) ͱϥονͷͲͪΒΛ༻͍Δ͔ͱ͍ͬͨɼಉ‫ॱࣜظ‬ংճ ࿏ͷಉ‫ظ‬ಈ࡞Λ‫ن‬ఆ͢ΔํࣜΛΫϩοΩϯάํࣜͱ͍͏ɽ ຊষͰ͸ɼओʹ‫ط‬ଘͷΫϩοΩϯάํࣜʹ͍ͭͯड़΂Δɽ ΫϩοΩϯάํࣜΛཧղ͢Δ্Ͱ͸ɼզʑ͕λΠϛϯάɾ μΠΞάϥϜ (t-diagram) ͱ‫Ϳݺ‬ਤΛ༻͍Δͱ౎߹͕Α. . . T. . . . VWDJH. δοΫͷ࣮ޮ஗Ԇͱ‫֓Ϳݺ‬೦͕ॏཁʹͳΔɽҎԼɼ2.1 અ Ͱ t-diagram ͱ࣮ޮ஗Ԇʹ͍ͭͯ঺հͨ͠‫ޙ‬ɼ2.2 અҎ߱. . G G. FON. ͍ɽ·ͨɼಛʹ TF ‫ݕ‬ग़Λߦ͏ΫϩοΩϯάํࣜͰ͸ɼϩ. Ͱɼ‫ط‬ଘͷΫϩοΩϯάํࣜʹ͍ͭͯड़΂Δɽ. . FON. [\]. W. G. G. . 2.1 λΠϛϯάɾμΠΞάϥϜͱೖྗ͹Β͖ͭ W[. ਤ 1ʢ্ʣͷճ࿏ʹ͓͍ͯɼ৴߸͕఻ΘΔ༷ࢠΛಉਤʢԼʣ ʹࣔ͢ɽಉਤʢԼʣͷਤΛɼզʑ͸ɼλΠϛϯάɾμΠΞά ϥϜ (t-diagram) ͱ‫ݺ‬ΜͰ͍Δɽ௨ৗͷλΠϜɾνϟʔ. W\. τ͕࿦ཧ஋-࣌ؒͷ 2 ࣍‫ݩ‬Λ࣋ͭʹରͯ͠ɼt-diagram ͸࣌ ؒ-ۭؒͷ 2 ࣍‫ݩ‬Λ࣋ͭɽ௨ৗͷλΠϜɾνϟʔτͰ͸ɼӈ ํ޲͕࣌ؒΛɼ্Լํ޲͕࿦ཧ஋Λද͢ɽλΠϜɾνϟʔ. WF\FOH. W]. τ͸ɼ࿦ཧ஋ͷ࣌ؒతมԽΛද‫͢ݱ‬Δ͕ɼ1 ຊͷ೾‫Ͱܗ‬ද ͢͜ͱ͕Ͱ͖Δͷ͸ճ࿏ͷಛఆͷ 1 ఺ͷৼΔ෣͍ʹ‫ݶ‬Β ΕΔɽෳ਺ͷ఺ʹ·͕ͨΔಈ͖Λ೺Ѳ͢ΔͨΊʹ͸ɼෳ਺. c 2013 Information Processing Society of Japan . WLPH. ਤ 1. WLPH. λΠϛϯάɾμΠΞάϥϜ (t-diagram) ͱ࣮ޮ஗Ԇ. 2.

(3) Vol.2013-ARC-206 No.6 2013/7/31. ৘ใॲཧֶձ‫ڀݚ‬ใࠂ IPSJ SIG Technical Report. ͨஈ֊Ͱ৴߸͸෺ཧతʹ͸ফࣦ͍ͯ͠Δ͕ɼԾ૝తʹ఺ઢ. 崳嵶嵷嵤嵪嵨崢. 崲崰崷嵶嵷嵤嵪嵨崢. ໼ҹͰද͢͜ͱʹ͢Δɽ. 崳嵦嵼嵦嵯嵨崢. t-diagram Ͱ͸ɼϩδοΫͷΫϦςΟΧϧɾύεͷ஗Ԇ ʹରԠ͢Δ໼ҹΛ੺Ͱඳ͘͜ͱͱ͠ɼͦͷ֯౓Λ 45◦ ͱܾ. 崳嵦嵼嵦嵯嵨崢. ೖྗ͹Β͖ͭͱλΠϛϯάɾμΠΞάϥϜ. ΊΔɽ͜ͷ໿ଋʹΑΓɼ͋ΔϩδοΫͷΫϦςΟΧϧɾύ εͷ஗Ԇ͸ɼt-diagram ্ͷϩδοΫʹରԠ͢ΔྖҬͷԣ ෯ʹΑͬͯද‫͢ݱ‬Δ͜ͱ͕Ͱ͖Δɽ͜ͷ͜ͱ͸ಛʹɼ?? અ ͰλΠϜɾϘϩʔΠϯάͷઆ໌Λ͢Δ্ͰॏཁͱͳΔɽ ࣮ࡍͷϩδοΫͰ͸ɼ͹Β͖ͭͷͨΊɼ஗Ԇ͸࿈ଓతʹ มԽ͢ΔɽͦͷͨΊɼ໼ҹͷଘࡏൣғ͸ɼϩδοΫͷ࠷খ. 嵷嵬嵰嵨崢. ਤ 2. ୯૬ FF(ࠨ) ͱೋ૬ϥονʢӈʣͷ t-diagram. ஗Ԇͷ໼ҹͱΫϦςΟΧϧɾύεͷ஗Ԇͷ੺໼ҹʹ্ԼΛ. Δঢ়ଶΛද͍ͯ͠Δɽ৴߸ͷઢ͕͜ͷ࣮ઢʹԊͬͯ఻͏༷. ‫·ڬ‬ΕͨྖҬͱͳΔɽ. ࢠ͸ɼͦͷؒϥον͕஋Λอ͍࣋ͯ͠Δ͜ͱΛද͢ɽΤο. t-diagram Ͱ͸ɼ໢ֻ͚Λࢪͯ͜͠ͷྖҬΛࣔ͢ɽ ࣮ޮ஗Ԇ ͋ΔϩδοΫʹ͓͍ͯ࠷‫׆ʹޙ‬ੑԽ͞Εͨύεͷ஗Ԇ. δɾτϦΨಈ࡞͸ɼϚελ–εϨʔϒΛ‫͍ޓ‬ҧ͍ʹ‫ه‬ड़͢ Δ͜ͱͰੜ͡Δ͔ܺؒΒ৴߸͕఻೻͢Δ༷ࢠͰද͢͜ͱ͕ Ͱ͖Δɽ. Λɼ͜ͷϩδοΫͷ࣮ޮ஗Ԇͱ‫͢ʹͱ͜Ϳݺ‬Δɽਤ 1 ͷ৔ ߹ɼ࣌ࠁ t = tz ʹ͓͍ͯΫϦςΟΧϧɾύεΛ௨ͬͨ৴߸ ͕౸ண͢Δ͸͕ͣͩɼϚεΫ͞ΕͨͨΊɼϩδοΫͷग़ྗ. d ͸มԽ͠ͳ͍ɽ͜ͷ৔߹ɼ࣮ޮ஗Ԇ͸ ty ͱͳΔɽ. 2.3 ೋ૬ϥονํࣜ ೋ૬ϥον͸ɼϚελ–εϨʔϒߏ଄Λ࣋ͭ FF Λߏ੒ ͢Δ 2 ͭͷϥονͷ͏ͪͷ 1 ͭΛɼϩδοΫͷத΄Ͳʹ. ࣌ࠁ t = ty ʹ͓͍ͯग़ྗ d ͕มԽͨ࣌͠ʹ͸࣮ޮ஗Ԇ. Ҡಈͨ͠΋ͷͱཧղ͢Δ͜ͱ͕Ͱ͖Δɽ୯૬ FF ํࣜͷ. ͕ ty Ͱ͋Δ͜ͱ͸෼͔Βͳ͍ɽ࣌ࠁ t = tz ʹ͓͍ͯ d ͕. 1 εςʔδ ʹ૬౰͢ΔϩδοΫΛɼ͜ͷϥον͕ೋ෼͢Δ. มԽ͠ͳ͔ͬͨ͜ͱΛ‫ॳͯݟ‬Ίͯ ty Ͱ͋ͬͨ͜ͱ͕෼͔. ‫ͳʹܗ‬Δɽ. Δɽ͜ͷΑ͏ʹɼ࣮ޮ஗Ԇ͸ࣄ‫ޙ‬తʹ෼͔Δ͜ͱʹ஫ҙ͞ Ε͍ͨɽ. t-diagram Ͱ͸࣮ޮ஗ԆʹରԠ͢Δ໼ҹΛଠ࣮ઢͰද͢ɽ ΫϦςΟΧϧɾύε͕‫׆‬ੑԽͨ͠৔߹ʹ͸ɼ45◦ ͷ੺໼ҹ Λߋʹଠͯ͘͠ද͢ɽ ೖྗ͹Β͖ͭͱ࣮ޮ஗Ԇ. ೋ૬ϥονͱ‫ͯͬݴ‬΋ɼ࣮ࡍʹ͸ɼೋ૬ͷΫϩοΫΛ༻ ͍Δඞཁ͸ͳ͍ɽਖ਼૬ͱ‫ٯ‬૬ͷ 2 छྨϥονΛ༻͍Δ͜ͱ ͰɼΫϩοΫ͸ʢσϡʔςΟൺ 50% ͷʣ୯૬ͱ͢Δ͜ͱ͕ Ͱ͖Δɽ ਤ 2 ӈ͕ɼೋ૬ϥονํࣜͷ t-diagram Ͱ͋Δɽ୯૬ FF Ͱ͸ϥον͕ৗʹด͍ͯ͡Δ͕ɼೋ૬ϥονํࣜͰ͸ϥο. ϩδοΫ΁ͷೖྗͷมԽͷ࢓ํʹΑͬͯग़ྗͷมԽͷ࢓. νͷ։͍͍ͯΔ͕۠ؒଘࡏ͍ͯ͠Δ͜ͱΛಛ௃ͱ͢Δɽ͜. ํ΋༷ʑͰ͋ΓɼͲͷύε͕࠷‫׆ʹޙ‬ੑԽ͞ΕΔ͔͸ຖ. ͷ։͍͍ͯΔ۠ؒΛར༻͢Δ͜ͱʹΑΓɼҎԼʹड़΂Δε. αΠΫϧҟͳΔɽͭ·Γ࣮ޮ஗Ԇ͸ɼೖྗͷมԽͷ࢓ํʹ. ςʔδؒͷλΠϜɾϘϩʔΠϯά͕ՄೳʹͳΔɽ. Αͬͯେ͖͘͹Βͭ͘ɽ͜ͷ͜ͱΛೖྗ͹Β͖ͭͱ‫Ϳݺ‬ɽ. ੩తλΠϜɾϘϩʔΠϯά. ೖྗ͹Β͖ͭ͸ɼଞͷ͹Β͖ͭʹൺ΂ͯඇৗʹେ͖͍ [8]ɽ ग़ྗ͕௚લͷαΠΫϧ͔ΒมԽ͠ͳ͔ͬͨ৔߹ʹ͸ɼ࣮ޮ ஗Ԇ͸࣮࣭ 0 ͱͳΔɽ͢ͳΘͪɼೖྗ͹Β͖ͭ͸ɼ0 ͔Β. ਤ 3 ͸εςʔδؒͷ஗ԆʹภΓ͕͋Δ৔߹ͷ୯૬ FF ํ ࣜʢࠨʣͱೋ૬ϥονํࣜʢӈʣͷ t-diagram Ͱ͋Δɽ ୯૬ FF ํࣜͰ͸ৗʹϥον͕ด͍ͯ͡Δঢ়ଶͷͨΊɼ. ΫϦςΟΧϧɾύε஗Ԇ·ͰมԽ͢ΔͷͰ͋Δɽଞͷ͹Β. ԾʹΫϩοΫͷ্ཱ͕ͪΓΑΓલʹ৴߸͕౸ୡ͍ͯͯ͠. ͖ͭʹΑΔ஗ԆͷมԽ͕ߴʑ਺े % ఔ౓Ͱ͋Δ͜ͱΛߟ͑. ΋ɼ৴߸͕࣍ͷεςʔδʹ఻೻͢ΔλΠϛϯά͕ΫϩοΫ. Δͱɼ͜ͷมԽͷ౓߹͍͸ඇৗʹେ͖͍ͱ‫͑ݴ‬Δɽ·ͨɼ. ͷ্ཱ͕ͪΔॠؒʹ‫ݶ‬ఆ͞Ε͍ͯΔͨΊɼεςʔδ͝ͱʹ. ϩδοΫͷग़ྗͷมԽ཰͸ 1/2 ఔ౓Ͱ͋Δ͜ͱ͕஌ΒΕͯ. ࣌ؒΛ༥௨Ͱ͖ͳ͍ɽͦͷͨΊɼ஗Ԇ͕େ͖͍εςʔδʹ. ͍Δɽ͢ͳΘͪɼ1/2 ఔ౓ͷߴ͍֬཰Ͱ࣮ޮ஗Ԇ͸ 0 ͱͳ. Αͬͯϫʔετ஗Ԇ͕ఆ·ΔͨΊɼ஗Ԇͷখ͍͞εςʔδ. Δ͜ͱʹ΋஫ҙ͢Δඞཁ͕͋Δɽ. Ͱ͸αΠΫϧɾλΠϜʹແବ͕ੜͯ͡͠·͏ɽ ೋ૬ϥονํࣜͰ͸ɼ୯૬ FF ํࣜͷ 1 εςʔδʹ૬౰. 2.2 ୯૬ FF ํࣜ. ͢ΔϩδοΫ͕ 2 ෼͞Ε͓ͯΓɼϩδοΫΛ௨ա͢Δ࣌ؒ. ਤ 2 ࠨ͕ɼ୯૬ FF ํࣜͷ t-diagram Ͱ͋ΔɽϚελ-ε. ΛεςʔδؒͰ༥௨͢Δ͜ͱ͕Ͱ͖ɼͦͷ݁ՌαΠΫϧɾ. Ϩʔϒ‫ܕ‬ͷ FF ͸‫ٯ‬૬Ͱಈ͘ϥονΛ 2 ͭ૊Έ߹ΘͤΔߏ. λΠϜ͕୹ॖͰ͖Δɽ͜ͷΑ͏ʹɼલ‫ޙ‬ͷεςʔδؒͰ࣌. ଄ΛͱΔɽ. ؒΛ༥௨͢Δख๏ΛλΠϜɾϘϩʔΠϯάͱ‫͏ݴ‬ɽ‫ޙ‬ड़͢. ಉਤʹ͓͍ͯɼFF ͷԼʹ͋Δ࣮ઢ͸ɼϥον͕ด͍ͯ͡. c 2013 Information Processing Society of Japan . ΔఏҊख๏ͷಈతλΠϜɾϘϩʔΠϯάͱ۠ผ͢ΔͨΊɼ. 3.

(4) Vol.2013-ARC-206 No.6 2013/7/31. ৘ใॲཧֶձ‫ڀݚ‬ใࠂ IPSJ SIG Technical Report 崳嵶嵷嵤嵪嵨崢. 崲崰崷崢. 崳嵦嵼嵦嵯嵨崢. 崳嵶嵷嵤嵪嵨崢. 崳嵦嵼嵦嵯嵨崢. 崲崰崷崢. 徸崢. 崲崰崷嵶嵷嵤嵪嵨崢. 崳嵦嵼嵦嵯嵨崢. 崲崰崷崢. 崳嵶嵷嵤嵪嵨崢. 崳嵦嵼嵦嵯嵨崢. 崳嵶嵷嵤嵪嵨崢. 嵺嵤嵶嵷嵨崢. 嵷嵬嵰嵨崢. ਤ 4. 嵷嵬嵰嵨崢. ਤ 3. ୯૬ FFʢࠨʣͱ Razorʢӈʣͷ t-diagram. ੩తλΠϜɾϘϩʔΠϯά 嵰嵤嵬嵱崢. ͜ͷઃ‫͚͓ʹ࣌ܭ‬ΔλΠϜɾϘϩʔΠϯάΛ੩తλΠϜɾ ϘϩʔΠϯάͱ‫Ϳݺ‬ɽ. 嵨嵵嵵嵲嵵崢. ͳ͓ɼઃ‫͍͓ͯʹܭ‬͸ɼ·ͣεςʔδؒͷ஗ԆΛόϥϯ 嵶嵫嵤嵧嵲嵺崢. 嵦嵯嵮崢. εͤ͞Δ͜ͱ͕؊ཁͰ͋ΓɼλΠϜɾϘϩʔΠϯάͷޮՌ Λੵ‫ۃ‬తʹར༻͢Δ͜ͱ͸ਪ঑͞Εͳ͍ɽ͜ͷੑ࣭͸ɼΫ ϩοΫɾεΩϡʔʹର͢Δ଱ੑʹޮՌ͕͋Γ [9]ɼ࣮ࡍʹ͸. 嵰嵤嵬嵱崢. εΩϡʔ଱ੑͷͨΊʹ࠾༻͞ΕΔ͜ͱ͕ଟ͍Α͏Ͱ͋Δɽ. 嵈嵤嵯嵶嵨崢嵐嵨嵪嵤嵷嵬嵹嵨崣崢. 2.4 Razor. 嵶嵫嵤嵧嵲嵺崢. ਤ 5ʢ্ʣʹɼRazor FF ͷճ࿏ߏ੒Λࣔ͢ [3]ɽRazor. FF ͸ɼ௨ৗͷ FFʢMain FFʣͱɼShadow Latch ʹΑͬ ͯߏ੒͞ΕΔɽShadow Latch ʹ͸ɼMain FF ΁ͷͦΕΑ ΓҐ૬ͷ஗ΕͨΫϩοΫ͕‫͞څڙ‬Ε͓ͯΓɼMain FF ͱ. 嵷嵬嵰嵨崢. ਤ 5 Razor ͷճ࿏ߏ੒ͱγϣʔτɾύε໰୊. Shadow Latch Ͱ 2 ճɼ৴߸ͷαϯϓϦϯάΛߦ͏ɽͦΕ Βͷ஋Λൺֱͯ͠ɼҟͳ͍ͬͯΕ͹ TF ͱͯ͠‫ݕ‬ग़͢Δɽ. ஗Ԇ੍໿͸ (1 + α)τ /1 εςʔδ ͱͳΓɼ୯૬ FF ํࣜΑ. ͳ͓ɼTF ‫ݕ‬ग़‫ޙ‬͸ɼύΠϓϥΠϯɾϑϥογϡͳͲɼΞʔ. Γ ατ ͚ͩվળ͞ΕΔɽ. ΩςΫνϟɾϨϕϧͷख๏ʹΑͬͯ TF ͔Βͷճ෮͕ߦΘ ΕΔ [3], [10]ɽ ਤ 4 ͸୯૬ FF ํࣜͱ Razor ͷ t-diagram Λൺֱͨ͠΋ ͷͰ͋ΔɽಉਤͰ͸ Main FF ͱ‫ٯ‬૬ͷɼ͢ͳΘͪɼ൒प‫ظ‬஗. ࣮ޮ஗ԆʹରԠ͢Δଠ໼ҹ͕‫ݕ‬ग़΢Οϯυ΢ͷ্୺ΑΓ ઌʹ౸ண͍ͯ͠Ε͹ɼTF ͱͳΒͳ͍ɽ͢ͳΘͪɼTF ͱͳ Βͳ͍࠷େ஗Ԇ੍໿͸ 1τ /1 εςʔδ ͱͳΔɽ. Razor ͷγϣʔτɾύε໰୊. ΕͨΫϩοΫΛ Shadow Latch ʹ‫͍ͯ͠څڙ‬Δɽt-diagram. ΫϩοΫɾεΩϡʔʹ‫ى‬Ҽ͢ΔϗʔϧυɾλΠϜҧ൓ͳ. ্ʹ͓͚Δ FF ͷԼͷᒵ৭ͷ࣮ઢ͸ɼTF ͷ‫ݕ‬ग़΢Οϯυ. Ͳɼγϣʔτɾύε͕‫ݪ‬ҼͰ஗Ԇ੍໿͕ຬͨ͞Εͳ͍໰୊. ΢Λද͍ͯ͠Δɽ‫ݕ‬ग़΢Οϯυ΢ͷɼ্୺Ͱ Main FF ͕ɼ. Λγϣʔτɾύε໰୊ͱ‫Ϳݺ‬ɽRazor ʹ͸ɼಛ༗ͷγϣʔ. Լ୺Ͱ Shadow Latch ͕৴߸ͷαϯϓϦϯάΛߦ͍ɼͦͷ. τɾύε໰୊͕͋Δɽ. ஋Λൺֱ͢Δɽ͕ͨͬͯ͠ɼ‫ݕ‬ग़΢Οϯυ΢ʹ࣮ޮ஗Ԇʹ. ਤ 5 Λ༻͍ͯɼRazor ͷγϣʔτɾύε໰୊Λઆ໌͢Δɽ. ରԠ͢Δଠ໼ҹ͕౸ண͍ͯ͠Ε͹ɼTF ͱͳΔՄೳੑ͕͋. Main FF ͱ Shadow Latch ͷ஋Λൺֱ͢Δ͜ͱͰ TF Λ‫ݕ‬. Δɽͨͩ͠ɼ‫਺ۮ‬ճมԽͯ͠‫ʹݩ‬໭ͬͨ৔߹ʹ͸ɼTF ͱ. ग़͢ΔɽShadow Latch ͕ਖ਼͍͠஋ΛαϯϓϦϯά͢Δͨ. ͳΒͳ͍ɽ. Ίʹ͸ɼϩδοΫͷγϣʔτɾύεΛ௨ͬͨ৴߸͕ Shadow. ࠷େ஗Ԇ੍໿. Latch ͷαϯϓϦϯάɾλΠϛϯάΑΓ΋‫ʹޙ‬౸ୡ͠ͳ͚. ୯૬ FF ํࣜͰ͸ɼΫϦςΟΧϧɾύεͷ஗ԆʹରԠ͢ ◦. Ε͹ͳΒͳ͍ɽ͞΋ͳ͍ͱɼਤʹࣔ͞Ε͍ͯΔΑ͏ʹɼ͋. Δ 45 ͷ੺ઢ͕࣍ͷΫϩοΫɾΤοδʹؒʹ߹͏ඞཁ͕͋. ΔϑΣʔζʹ͓͍ͯγϣʔτɾύεΛ௨ͬͨ৴߸͕ɼલͷ. ΔͨΊɼ࠷େ஗Ԇ੍໿͸ 1τ /1 εςʔδ ͱͳΔɽ. ϑΣʔζͷ৴߸ͱʮࠞ͟Δʯ ɽͦͷ݁ՌɼShadow Latch ͕. ҰํɼRazor Ͱ͸ɼΫϦςΟΧϧɾύεͷ஗ԆʹରԠ͢ ◦. ຊདྷͱ͸ҟͳΔ஋ΛαϯϓϦϯά͢ΔՄೳੑ͕͋Δɽͦͷ. Δ 45 ͷ੺ઢ͕‫ݕ‬ग़΢Οϯυ΢ͷԼ୺·Ͱʹ౸ண͢Ε͹ɼ. ݁Ռɼ‫ݕޡ‬ग़ (false positive) ͱͳΕ͹໰୊ͳ͍͕ɼ‫ݕ‬ग़࿙. TF ͱͯ͠ॲཧ͢Δ͜ͱ͕Ͱ͖Δɽ͕ͨͬͯ͠ɼαΠΫϧɾ. Ε (false negative) ͱͳΔͱக໋తͰ͋Δɽ. λΠϜʹର͢Δ‫ݕ‬ग़΢Οϯυ΢ͷׂ߹Λ α ͱ͢Δͱɼ࠷େ. c 2013 Information Processing Society of Japan . ͜ͷͨΊ Razor ͸ɼRazor ಛ༗ͷ࠷খ஗Ԇ੍໿Λੜ͡Δɽ. 4.

(5) Vol.2013-ARC-206 No.6 2013/7/31. ৘ใॲཧֶձ‫ڀݚ‬ใࠂ IPSJ SIG Technical Report. ஗Ԇͷ஋ E(i) Λ஗Ԇͷࢧग़ɼFF ΍ϥονʹΑΓ৴߸ͷ มԽ͕࣍εςʔδʹ఻ൖ͠ͳ͍࣌ؒ I(i) Λ஗Ԇͷऩೖͱ ৿৓嵖嵄崢 ৿৓嵖嵄崢. ఆٛ͢Δɽ୯૬ FF ํࣜ΍ Razor ͷ৔߹ɼ1 εςʔδຖʹ. I(i) = τ ɼೋ૬ϥονํࣜ΍ఏҊख๏ͷ৔߹ɼ0.5 εςʔδ ຖʹ I(i) = 1/2τ ͷ஗Ԇͷऩೖ͕͋Δɽͦͯ͠ɼεςʔδʹ. 嵺嵤嵶嵷嵨崢. ͓͚Δ஗ԆͷऩࢧΛ D(i) = I(i) − E(i) Ͱද͠ɼD(i) ≥ 0 ೚భभ஧ஊऋ崢 ྸ஋慓慙ৃ়懙嵖嵈. ͢Δɽ ࠓɼL0 ͱ L1 ͷؒͷεςʔδͰ L0 ͷ։͍ͨॠ͔ؒΒ৴. 嵷嵬嵰嵨崢. ਤ 6. ͷ৔߹Λ஗ԆͷࠇࣈɼD(i) < 0 ͷ৔߹Λ஗Ԇͷ੺ࣈͱఆٛ. ߸͕఻೻͠ɼ࣮ޮ஗Ԇ E(1) = 3/4τ Ͱ L1 ͷ஋͕มԽͨ͠ ೋ૬ϥονํࣜʢࠨʣͱఏҊख๏ʢӈʣͷ t-diagram. ͱ͢Δɽ͜ͷ࣌ɼ͜ͷεςʔδʹ͓͚Δ஗Ԇͷऩࢧ D(1) ͸ɼD(1) = 1/2τ − 3/4τ = −1/4τ ͱͳΓɼ஗Ԇͷ੺ࣈ͕ੜ. ਤ 5 Ͱ͸ɼShadow Latch ͷαϯϓϦϯάΛ 0.5τ ஗Βͤͯ. ·ΕΔɽԾʹɼ࣮ޮ஗Ԇ E(1) = 1/4τ Ͱ L1 ͷ஋͕มԽ͠. ͍ΔͨΊɼ࠷খ஗Ԇ੍໿͸ 0.5τ /1 εςʔδ ͱͳΔɽલઅ. ͨͱ͢ΔͱɼD(1) = 1/2τ − 1/4τ = 1/4τ ͱͳΓɼ஗Ԇͷ. ͱಉ༷ʹɼαΠΫϧɾλΠϜʹର͢Δ‫ݕ‬ग़΢Οϯυ΢ͷׂ. ࠇࣈ͕ੜ·ΕΔɽಉਤ྘৭ͷ఺ઢ͸ɼଛӹ෼‫ذ‬ʢD(i) = 0. ߹Λ α ͱ͢Δͱɼ࠷খ஗Ԇ੍໿͸ ατ /1 εςʔδ ͱͳΓɼ. ͱͳΔ‫ڥ‬քʣΛද͍ͯ͠Δɽ. ୯૬ FF ํࣜΑΓ ατ ͚ͩ‫ͳ͘͠ݫ‬Δɽγϣʔτɾύεʹ. D(1) = −1/4τ ͷঢ়ଶͰɼL1 ͱ L2 ͷؒͷεςʔδͰΫ. ஗ԆૉࢠΛૠೖ͢ΔͳͲͯ͠ɼϩδοΫͷ࠷খ஗ԆΛ ατ. ϦςΟΧϧɾύεʢ஗Ԇ τ ʣ͕‫׆‬ੑԽͨ͠৔߹ɼ͜ͷεςʔ. Ҏ্ʹ͢Δඞཁ͕͋Δɽ. δʹ͓͚Δ஗Ԇͷऩࢧ D(2) ͸ɼD(2) = 1/2τ − τ = −1/2τ. ͜ͷΑ͏ʹ Razor ʹ͸ɼ࠷େͱ࠷খ஗Ԇ੍໿ͷؒʹɼα ΠΫϧɾλΠϜʹର͢Δ‫ݕ‬ग़΢Οϯυ΢ͷׂ߹ α Λհ͠ ͯɼ௚઀తͳτϨʔυΦϑ͕ଘࡏ͢Δɽ. 3. ఏҊख๏. ͱͳΔɽ͜ͷ࣌ɼL0 ͔Β L2 ·Ͱͷεςʔδʹ͓͚Δ஗ Ԇͷऩࢧͷྦྷੵ͸. . D(i) = D(1) + D(2) = −3/4τ ͱ. ͳΔɽఏҊख๏Ͱ͸ɼ͜ͷΑ͏ʹ஗Ԇͷ੺ࣈ͕ྦྷੵ͠ɼ. . −τ ≤. D(i) < −1/2τ ͱͳͬͨ৔߹Λ TF ͱͯ͠‫ݕ‬ग़. ͢Δɽ. ຊষͰ͸ɼೋ૬ϥονํࣜͱ TF ‫ݕ‬ग़Λ૊Έ߹ΘͤͨΫ. ࣍ʹɼL1 ͱ L2 ͷؒͷεςʔδͰ஗Ԇͷ୹͍γϣʔτɾ. ϩοΩϯάํࣜΛఏҊ͢Δɽ͜ΕʹΑΓɼಈతλΠϜɾϘ. ύεʢ஗Ԇ 1/8τ ʣ͕‫׆‬ੑԽͨ͠৔߹Λߟ͑Δɽ͜ͷ࣌ɼ. ϩʔΠϯά͕ՄೳʹͳΔɽҎԼɼ3.1 અͰಈతλΠϜɾϘ ϩʔΠϯάʹ͍ͭͯৄ͘͠औΓ্͛Δɽ3.2 અͰ‫ط‬ଘͷ TF. D(2) = 1/2τ − 1/8τ = 3/8τ Ͱɼ஗Ԇͷࠇࣈ͕ੜ·Εɼ஗ D(i) = −1/4τ + 3/8τ = 1/8τ ͷࠇࣈ Ԇͷऩࢧͷྦྷੵ΋. ‫ݕ‬ग़ख๏Ͱ͋Δ Razor ͱൺֱͯ͠ɼఏҊख๏ͷಛ௃΍༏Ґ. ͱͳΔɽ. ੑΛࣔ͢ɽ3.3 અͰఏҊख๏ͷճ࿏ߏ੒Λड़΂Δɽ. ͜ͷΑ͏ʹఏҊख๏Ͱ͸ϥονͷ։͍͍ͯΔ۠ؒΛར༻ ͢Δ͜ͱͰɼ஗Ԇͷ੺ࣈͷྦྷੵΛղফ͢Δ͜ͱ͕ՄೳͰ͋. 3.1 ಈతλΠϜɾϘϩʔΠϯά. Δɽೖྗ͹Β͖ͭʹண໨ͨ͠ɼ࣮ޮ஗ԆΛ༥௨ͤ͞Δ͜ͷ. ਤ 6 ͸ɼೋ૬ϥονํࣜͱఏҊख๏ͷ t-diagram Λൺֱ. ࣌ؒͷି͠आΓͷ͜ͱΛಈతλΠϜɾϘϩʔΠϯά ͱ‫ݺ‬. ͨ͠΋ͷͰ͋Δɽ2.3 અͰड़΂੍ͨ໿্ɼೋ૬ϥονํࣜ. Ϳɽt-diagram ্ʹ͓͚Δɼ௚ઢ໼ҹ͕ͭͳ͕ͬͯεςʔ. Ͱ͸৴߸͸ඞͣ࣍ͷϥον͕ด͍ͯ͡Δ‫ʹؒظ‬౸ண͠ͳ. δؒΛ఻೻͢Δ༷ࢠ͸ಈతλΠϜɾϘϩʔΠϯάͷޮՌΛ. ͚Ε͹ͳΒͣɼϥον͕։͍͍ͯΔ‫ؒظ‬͸‫ݪ‬ଇ࢖͏͜ͱ͕. ද͍ͯ͠Δͱ͍͑Δɽ. Ͱ͖ͳ͍ɽ֤εςʔδͰΫϦςΟΧϧɾύε͕‫׆‬ੑԽ͠ͳ. ͳ͓ɼ஗Ԇͷऩࢧͷྦྷੵ͕ࠇࣈʹͳͬͨ৔߹͸ɼϥον. ͔ͬͨͱͯ͠΋ɼϥον͕։͘·Ͱ৴߸ͷ఻೻͸଴ͨͳ͚. Ln ͕ด͍ͯ͡Δঢ়ଶͰ஋͕มԽͨ͜͠ͱʹͳΔͷͰɼ࣍. Ε͹ͳΒͳ͍ɽ. ͷεςʔδʹ৴߸͕఻೻͢ΔλΠϛϯά͸ϥονͷ։͘ॠ. ఏҊख๏Ͱ͸ೋ૬ϥονํࣜʹΑͬͯຊདྷతʹ͸ར༻Մ. . ؒͱͳΔɽͦͷͨΊɼ. D(i) ≥ 0 ͷ৔߹ɼ࣍εςʔδʹ D(i) = 0 ͱͯ͠‫ݟ‬Δɽ. ೳͰ͋ͬͨ͜ͷϥονͷ։͍͍ͯΔ‫ؒظ‬ΛɼTF ‫ݕ‬ग़Λઃ. ͓͍ͯྦྷੵͨ͠ࠇࣈͷ෼Λࣺͯɼ. ͚Δ͜ͱʹΑΓར༻͢Δɽ͜ΕʹΑΓɼಈ࡞࣌ʹ֤εςʔ. ࠷େ஗Ԇ੍໿. δͰ࣮ޮ஗ԆΛ༥௨͢Δ͜ͱ͕ՄೳͱͳΔɽ ࣮ޮ஗ԆΛ༥௨͢Δͱ͸ͲͷΑ͏ͳ͜ͱ͔ʹ͍ͭͯɼਤ 7. ࠶౓ɼਤ 6 ʹண໨͢ΔɽఏҊख๏Ͱ͸ɼ஗Ԇͷ੺ࣈ͕ྦྷ. . ੵ͠ɼ. D(i) = −τ ͱͳͬͨ৔߹Λ TF ‫ݕ‬ग़‫ݶ‬քͱͳΔΑ. ʹ͓͍ͯઆ໌͢Δɽਤ 7 ͸ఏҊख๏ͷ t-diagram Λ֦େ͠. ͏αΠΫϧɾλΠϜΛఆΊΔɽ֤εςʔδʹ͓͍ͯੜ͡͏. ͨ΋ͷͰ͋Δɽઆ໌ͷͨΊɼ֤ύΠϓϥΠϯɾϥονʹ L0 ɼ. Δɼ஗Ԇͷ੺ࣈͷ࠷େ஋͸ D(i) = −1/2τ Ͱ͋Δɽͦͷͨ. L1 ɼL2 ͱ໊લΛ෇͚Δɽ. Ίɼ. Ҏ߱ɼϥον Li−1 ͱ Li ͷؒͷεςʔδʹ͓͚Δ࣮ޮ c 2013 Information Processing Society of Japan . . D(i) = −1/2τ ͷঢ়ଶ͔ΒΫϦςΟΧϧɾύε͕‫׆‬ D(i) = −τ ʹͳΔ৔߹Λϫʔετ஗Ԇͷ‫ڥ‬քͱ. ੑԽ͠ɼ. 5.

(6) Vol.2013-ARC-206 No.6 2013/7/31. ৘ใॲཧֶձ‫ڀݚ‬ใࠂ IPSJ SIG Technical Report. 嵎崲崢. 嵎崴崢. 嵎崳崢. ϭͬϰʏ. 嵎崲崢. 嵎崴崢. 嵎崳崢. ೚భभహஊ崑. ‫ܦ‬ሺͳሻٙ崳崱崶忋崢. ೚భभྸ஋ऋహஊ৲崑. ^W͗ϭͬϴʏ. σ ‫ܦ‬ሺ݅ሻٙ崳崱崺忋崢崢崢崢 ‫ڀ‬崢崢崲崢 ;σ ‫ܦ‬ሺ݅ሻ ൒ Ͳ їσ ‫ܦ‬ሺ݅ሻ ൌ ͲͿ. ϯͬϰʏ. 嵐嵲崢嵨嵵嵵嵲嵵崢. ‫ܦ‬ሺͳሻٙ崯崳崱崶忋崢 σ ‫ܦ‬ሺ݅ሻ崿崢崯崵崱崶忋崢崢 ‫ڀ‬崢嵖嵈崢. ೚భभ஧ஊ崑. 嵖嵈崢. ೚భभ஧ஊऋྸ஋崑. W͗ʏ. ଵ. ;െ߬ ൑ σ ‫ܦ‬ሺ݅ሻ ൏ െ ߬ ଶ їd&Ϳ. 嵷嵬嵰嵨崢. ਤ 7. ಈతλΠϜɾϘϩʔΠϯά. 嵷嵬嵰嵨崢. ਤ 8. RazorʢࠨʣͱఏҊख๏ʢӈʣͷ t-diagram. ఆΊΔʢਤ 6 ӈɼ੺఺ઢʣ ɽ͢ͳΘͪɼϥον Ln−1 ͷด͡. 嵦嵵嵬嵷嵬嵦嵤嵯崢. Δ্୺͔Βϥον Ln ͷ‫ݕ‬ग़΢Οϯυ΢ͷԼ୺·Ͱ͕ϫʔ ετ஗Ԇͷ‫ڥ‬քͱͳΔɽ. 嵶嵫嵲嵵嵷崢. ͜ͷΑ͏ʹ͢ΔͱɼΫϦςΟΧϧɾύεͷ஗ԆʹΑͬͯ. 嵕嵫嵤嵧嵲嵺崢. 嵶嵫嵲嵵嵷崢. 嵔嵤嵽嵲嵵崢嵎嵤嵷嵦嵫崢. 嵏嵤嵬嵱崢. ϦςΟΧϧɾύεͷ஗ԆʹΑܾͬͯఆͰ͖Δɽ. 嵕嵫嵤嵧嵲嵺崢. ͳ͘ɼαΠΫϧɾλΠϜΛ 0.5 εςʔδ෼ͷϩδοΫͷΫ. 嵦嵵嵬嵷嵬嵦嵤嵯崢. 嵏嵤嵬嵱崢. ͜ΕʹΑΓɼϥονͷ։͍͍ͯΔ۠ؒΛར༻Ͱ͖Δ͚ͩͰ. 嵶嵫嵲嵵嵷崢. ੸ৼ懁憞憜崢. ఆΊΒΕΔϫʔετ஗Ԇͷ‫ڥ‬ք͕ t-diagram ্ʹ͓͍ͯ֊ ஈঢ়ͱͳΓɼαΠΫϧɾλΠϜΛ٧ΊΔ͜ͱ͕ՄೳͱͳΔɽ. 嵦嵵嵬嵷嵬嵦嵤嵯崢. 嵧嵨嵯嵤嵼崢. 嵦嵵嵬嵷嵬嵦嵤嵯崢. 嵶嵫嵲嵵嵷崢. 嵧嵨嵯嵤嵼崢. 嵔嵤嵽嵲嵵崢嵎嵤嵷嵦嵫崢. ઀੧ু১崢. ͜ ͷ ͜ ͱ ͔ Β ɼఏ Ҋ ख ๏ ͷ ࠷ େ ஗ Ԇ ੍ ໿ ͸ ɼ. 1τ /0.5 εςʔδ ͱද͢͜ͱ͕Ͱ͖ɼ୯૬ FF ํࣜ΍ೋ. ਤ 9. ఏҊख๏ͷճ࿏ߏ੒. ૬ϥονํࣜʹൺ΂ɼ࠷େ 2 ഒͷಈ࡞प೾਺ͷ޲্Λ‫ࠐݟ‬ Ή͜ͱ͕Ͱ͖Δɽ. TF Λ‫ݕ‬ग़͢ΔɽಈతλΠϜɾϘϩʔΠϯάʹΑΓɼ͋Δ εςʔδͰΫϦςΟΧϧɾύεͷΑ͏ͳ஗Ԇͷେ͖͍ύε. 3.2 Razor ͱఏҊख๏ͷൺֱ ಈతλΠϜɾϘϩʔΠϯάͷޮՌ͸ Razor ͱൺֱ͢Δ͜ ͱͰɼ͞Βʹ໌֬ͳ΋ͷʹͳΔɽਤ 8 ͸ Razor ͱఏҊख๏. ͕‫׆‬ੑԽͨ͠ͱͯ͠΋ɼͦͷ‫ޙ‬ͷεςʔδͰ஗Ԇͷখ͍͞ ύε͕‫׆‬ੑԽ͢Δ͜ͱͰɼ஗Ԇͷ੺ࣈͷྦྷੵΛ‫ݮ‬Β͠ɼTF ͷൃੜΛ཈͑Δ͜ͱ͕Ͱ͖ΔͷͰ͋Δɽ. ͷ t-diagram Ͱ͋Δɽ. Razor ͸ FF Λ༻͍ͨ TF ‫ݕ‬ग़ճ࿏Ͱ͋ΔͨΊλΠϜɾ. 3.3 ճ࿏ߏ੒. ϘϩʔΠϯά͕Ͱ͖ͳ͍ɽલड़ͨ͠Α͏ʹɼRazor ͸ 1 ε. ਤ 9 ͸ఏҊख๏ͷճ࿏ߏ੒Ͱ͋Δɽਤ 9 ্͸ೋ૬ϥον. ςʔδຖʹ I(i) = τ ͷ஗Ԇͷऩೖ͕͋Δɽ͔͠͠ɼԾʹ࣮. ͷճ࿏ͷུ֓ਤͰ͋ΔɽϩδοΫͷγϣʔτɾύεͱΫϦ. ޮ஗Ԇͷ஋͕ E(i) ≤ τ Ͱεςʔδʹ͓͚Δ஗Ԇͷऩࢧ͕. ςΟΧϧɾύεͱ͕ɼ͋Δήʔτʢਤத˓ҹʣͰ߹ྲྀͨ͠. D(i) ≥ 0 ͰࠇࣈͰ͋ͬͯ΋ɼ࣍ͷΫϩοΫɾΤοδ·Ͱ଴. ‫ޙ‬ɼϥονʹ઀ଓ͞Ε͍ͯΔɽ. ͨͳ͚Ε͹ͳΒͣɼ࣍ͷεςʔδʹ஗ԆͷࠇࣈΛ࣋ͪӽ͢. ਤ 9 Լ͸ఏҊख๏ͷճ࿏ͷུ֓ਤͰ͋ΔɽTF ‫ݕ‬ग़ͷͨ. ͜ͱ͸Ͱ͖ͳ͍ɽͦͷͨΊɼ֤εςʔδʹ͓͍ͯಠཱʹ஗. Ίʹɼ֤ϥονʹ‫ٯ‬૬Ͱಈ࡞͢Δ Shadow Latch ͱαϯϓ. Ԇͷऩࢧ D(i) Λ‫͚ͳݟ‬Ε͹ͳΒͳ͍ɽ. Ϧϯά͞Εͨ஋Λൺֱ͢Δ XOR ήʔτΛ௥Ճ͢ΔɽRazor. ࣮ޮ஗Ԇͷ஋͕ E(i) > τ ͱαΠΫϧɾλΠϜΛ௒͑ɼ஗. Ͱ༻͍ΒΕΔ Razor FF ͷ Main FF Λϥονʹஔ͖‫͑׵‬. Ԇͷऩࢧ͕ D(i) < 0 Ͱ੺ࣈͱͳͬͨ࣌఺Ͱɼඞͣ TF ͱ͠. ͨߏ଄ͱͳΔɽ. ͯ‫ݕ‬ग़͢ΔɽTF ͕‫ݕ‬ग़͞ΕΔ͝ͱʹճ෮ॲཧ͕ߦΘΕΔ. ήʔτͷೋॏԽ. ͨΊɼͦͷճ෮Φʔόʔϔου͸ແࢹͰ͖ͳ͍΋ͷͱͳΔɽ. 2.4 અͰड़΂ͨΑ͏ʹɼTF ‫ݕ‬ग़ʹΑΓ࠷େ஗Ԇ੍໿Λ. ҰํɼఏҊख๏Ͱ͸ɼϩδοΫ্ͷશ஗ԆͷଘࡏྖҬΛ. ؇࿨͢ΔͨΊʹ͸ɼ‫ݕ‬ग़‫ؒظ‬෼ͷ࠷খ஗Ԇ੍໿Λຬͨ͢Α. ϥονͷ։͍͍ͯΔ۠ؒʹ΋޿͛Δ͜ͱͰɼෳ਺εςʔδ. ͏ʹɼϩδοΫͷγϣʔτɾύεʹ஗ԆΛૠೖ͠ɼ‫ݕ‬ग़‫ظ‬. ؒʹ౉Δଟஈͷύε͕‫ܗ‬੒͞ΕΔɽ͜ΕʹΑΓɼ֤εςʔ. ؒΛ֬อ͠ͳ͚Ε͹ͳΒͳ͍ɽ. δಠཱͰ஗Ԇͷऩࢧ D(i) Λ‫ݟ‬ΔͷͰ͸ͳ͘ɼશεςʔδʹ. D(i) Λ‫ݟ‬Δ͜ͱ͕ՄೳͱͳΔɽ ͓͚Δ஗Ԇͷऩࢧͷྦྷੵ D(i) < −1/2τ ͱͳͬͨ৔߹ʹ ஗Ԇͷ੺ࣈͷྦྷੵ͕ c 2013 Information Processing Society of Japan . ͜ͷ͜ͱ͸ఏҊͷࠜ‫͋Ͱװ‬ΔಈతλΠϜɾϘϩʔΠϯά ͷޮՌΛബΊͯ͠·͏ɽਤ 10(ࠨ) ͸ɼ୯७ʹϩδοΫͷ γϣʔτɾύεʹ஗ԆΛૠೖͨ͠৔߹ͷ t-diagram Λද͠. 6.

(7) Vol.2013-ARC-206 No.6 2013/7/31. ৘ใॲཧֶձ‫ڀݚ‬ใࠂ IPSJ SIG Technical Report. 嵦嵯嵮. A. 嵦嵯嵮. O 嵰嵤嵬嵱. I0. 嵰嵤嵬嵱. C. 嵖嵈. 嵖嵈嵶嵫嵤嵧嵲嵺. I1. 嵶嵫嵤嵧嵲嵺. 嵃嵷嵬嵰嵨. 嵄. 嵷嵬嵰嵨. 嵅嵰嵤嵬嵱嵤嵬嵱. 嵦嵵嵬嵷嵬嵦嵤嵯. 嵰嵤嵬嵱嵬嵱. 嵦嵵嵬嵷嵬嵦嵤嵯. (cell LUT2 « (port I0 (direction INPUT)) (port I1 (direction INPUT)) (port O (direction OUTPUT)) « ) « (instance A « cellRef /87

(8) «

(9) (instance B « cellRef LUT2

(10) «

(11) (instance C « cellRef LUT2

(12) «

(13) (net n0 (joined (portRef O (instanceRef A)) (portRef I0 (instanceRef B)) (portRef I1 (instanceRef C)) )) «. B. 嵱嵨嵷嵩嵵嵲嵰. ਤ 10. 嵶嵫嵲嵵嵷. 嵧嵨嵯嵤嵼嵼. 嵶嵫嵤嵧嵲嵺. 嵧嵨嵯嵤嵼. 嵶嵫嵤嵧嵲嵺. 嵶嵫嵲嵵嵷. 嵷嵲嵺嵨嵬嵪嵫嵷. 崳崲. ਤ 11. ೋॏԽͷඞཁੑ. άϥϑ΁ͷม‫׵‬. ͍ͯΔɽਤத੨৭ͷྖҬΛ‫ݟ‬ΔͱɼϩδοΫͷ࠷খ஗Ԇ͕. ࣜͷద༻ΛࣗಈͰߦ͏πʔϧͷ։ൃΛਐΊ͍ͯΔɽຊষͰ. ‫ݕ‬ग़΢Οϯυ΢ͷ෼͚ͩ৳ͼͯ͠·͍ͬͯΔɽಈతλΠ. ͸ɼ͜ͷπʔϧͷߏ੒๏ʹ͍ͭͯड़΂Δɽ. ϜɾϘϩʔΠϯάͷޮՌͱ͸ɼ࣮ޮ஗Ԇͷ஋͕খ͍͜͞ͱ. ͜ͷπʔϧ͸άϥϑ΁ͷม‫׵‬ɼεςʔδ෼ׂɼೋ૬ϥο. Ͱ஗ԆͷࠇࣈΛੜΈɼ஗Ԇͷ੺ࣈͷྦྷੵΛղফ͢Δ͜ͱͰɼ. νԽɼTF ‫ݕ‬ग़‫෇ߏػ‬༩ͱ͍͏ 4 ͭͷϓϩηε͔Βߏ੒͞. ࣮ޮ஗Ԇͷฏ‫ͮ͘جʹۉ‬ಈ࡞Λ࣮‫͢ݱ‬Δ͜ͱʹ͋Δɽ͜Ε. ΕΔɽҎԼɼ֤ϓϩηεͷ࢓༷ɼͦΕΛຬͨͨ͢Ίͷཁ݅. Ͱ͸ɼ஗ԆͷࠇࣈΛੜΉύε͕ଘࡏ͠ͳ͍͜ͱʹͳΓɼಈ. Λྻ‫͠ڍ‬ɼಈ࡞Λ࣮‫͢ݱ‬ΔΞϧΰϦζϜΛड़΂Δɽ. తλΠϜɾϘϩʔΠϯάͷޮՌΛ‫ظ‬଴Ͱ͖ͳ͘ͳΔɽ ͜͜ͰɼTF ‫ݕ‬ग़͸ɼ‫ݕ‬ग़‫ؒظ‬தʹมԽͨ͠ Shadow Latch ͷ஋ͱɼ‫ݕ‬ग़‫ؒظ‬લʹอ࣋͞Εͨ Main Latch ͷ஋Λൺֱ. 4.1 άϥϑ΁ͷม‫׵‬ ద༻πʔϧͰ͸·ͣɼEDIFʢElectronic Design Inter-. ͢Δ͜ͱͰߦΘΕΔ͜ͱʹண໨͢Δɽ͢ͳΘͪɼ‫ݕ‬ग़‫ؒظ‬. charge Formatʣ‫͔ॻͰࣜܗ‬Εͨ൚༻ͷճ࿏ΛಡΈࠐΈɼFF. த͸ɼShadow Latch ͕։͍͓ͯΓɼMain Latch ͸ดͯ͡. ΍ೖྗ/ग़ྗϙʔτɼήʔτͱ͍ͬͨճ࿏தͷૉࢠΛϊʔ. ͍Δɽ͜ͷ͜ͱ͔ΒɼRazor ͷγϣʔτɾύε໰୊ͷຊ࣭. υɼૉࢠؒͷ഑ઢΛΤοδͱ͢Δάϥϑ΁ͱม‫͢׵‬Δɽ͜. ͸ɼShadow Latch ͷ஋͕γϣʔτɾύεͷ‫׆‬ੑԽʹΑͬ. ͷάϥϑΛ‫ʹݩ‬ɼఏҊํࣜͷద༻Λߦ͍ͬͯ͘ɽ. ͯมԽͯ͠͠·͏͜ͱͱΘ͔Δɽ. ద༻‫ޙ‬͸ɼάϥϑ͔Β EDIF ΁ͷॻ͖໭͠Λߦ͏ɽͦͷ. ͜ͷ఺ʹண໨͠ɼఏҊͷճ࿏͸ɼγϣʔτɾύεͱΫϦ. ͨΊʹɼάϥϑͱ EDIF ͱͷରԠؔ܎Λ໌֬ʹ͢Δඞཁ͕. ςΟΧϧɾύεͷ߹ྲྀ͢ΔήʔτΛೋॏԽ͠ɼMain Latch. ͋Δɽਤ 11 ʹͦͷ༷ࢠΛࣔ͢ɽEDIF ͸ S ࣜͷϦετߏ. ͱ Shadow Latch ʹࢸΔύεͷ‫ܦ‬࿏Λ෼཭͢Δߏ੒ΛऔΔɽ. ଄Ͱ‫ه‬ड़͞Ε͍ͯΔɽ͜ΕΛϦετͷσʔλߏ଄ʹೖΕɼ. Shadow Latch ͷγϣʔτɾύεʹͷΈ஗ԆΛૠೖ͢Δ͜. ϊʔυ΍Τοδʹ࣋ͨͤΔɽ͜ΕʹΑΓɼఏҊํࣜΛద༻. ͱͰɼ‫ݕ‬ग़۠ؒΛ֬อ͢ΔɽMain Latch ͷγϣʔτɾύ. ͨ͠‫ޙ‬ͷάϥϑ͔ΒɼEDIF ʹॻ͖໭͢͜ͱ΋ՄೳʹͳΔɽ. εʹ͸஗Ԇ͕ૠೖ͞Εͯͳ͍ͷͰɼϩδοΫͷ࠷খ஗Ԇ͸ อͨΕΔɽ ਤ 10(ӈ) ʹ͸ఏҊͷճ࿏ߏ੒Ͱγϣʔτɾύε໰୊ͷର. 4.2 εςʔδ෼ׂ ઌʹड़΂ͨೋ૬ϥονԽ΍ Razor ͷૠೖͱ͍ͬͨఏҊํ. ࡦΛߦͬͨ৔߹ͷ t-diagram Ͱ͋Δɽt-diagram ʹ͓͍ͯ. ࣜͷద༻͸ɼ֤εςʔδ͝ͱʹߦͳΘΕΔɽͦͷͨΊʹɼ. ͸ϑΣʔζ͕ʮࠞͬͯ͟ʯ͍ΔΑ͏ʹ‫͑ݟ‬Δ͕ɼ֤ϑΣʔ. ਤ 12 ʹࣔ͢Α͏ʹɼճ࿏શମͷάϥϑΛɼFF ΍ೖྗ/ग़. ζͷ৴߸ͷ‫ܦ‬࿏ͷҧ͍ʹΑΓɼ࣮ࡍʹ͸ϑΣʔζͷ৴߸͕. ྗϙʔτʹ‫·ڬ‬ΕͨϩδοΫ෦෼Ͱ੾Γग़͠ɼεςʔδ୯. ʮࠞ͟Δʯ͜ͱ͸ͳ͍ɽ. 4. ద༻ࣗಈԽπʔϧ զʑ͸ҎલɼϦϓϧΩϟϦʔɾΞμʔ΍ΩϟϦʔϧοΫ ΞϔουɾΞμʔΛ༻͍ͨΞοϓɾΧ΢ϯλͷΑ͏ͳൺֱ. Ґͷάϥϑʹ෼ׂ͢Δඞཁ͕͋Δɽ ҎԼɼFF ΍ೖྗ/ग़ྗϙʔτͷϊʔυΛ‫ڥ‬քϊʔυɼϩ δοΫΛߏ੒͢ΔૉࢠͷϊʔυΛϩδοΫϊʔυͱ‫͜Ϳݺ‬ ͱʹ͢Δɽ ຬͨ͢΂͖ཁ݅. త؆୯ͳճ࿏ʹର͢ΔఏҊख๏ͷద༻Λɼख࡞‫ʹۀ‬ΑΓߦ. ճ࿏શମͷάϥϑΛਖ਼͘͠εςʔδ୯Ґͷάϥϑʹ෼ׂ. ͍ɼධՁΛߦͬͨ [7]ɽ͔͠͠ɼϓϩηοαͷΑ͏ʹճ࿏‫ن‬. ͢ΔͨΊʹ͸ɼόοΫΤοδ΍ϑΥϫʔυΤοδ͕ଘࡏ͠ɼ. ໛͕େ͖͍΋ͷʹର͢Δద༻Λख࡞‫͏ߦͰۀ‬ͷ͸ɼෆՄೳ. ͲͷΑ͏ʹεςʔδ෼ׂ͢΂͖͔Θ͔Γʹ͍͘ϩδοΫʹ. ʹ͍ۙɽ. ରͯ͠΋ਖ਼͘͠෼ׂΛߦ͏ඞཁ͕͋Δɽਤ 13 ʹͦͷྫΛ. ͦ͜Ͱ‫ࡏݱ‬ɼ൚༻ͷճ࿏Λάϥϑʹམͱ͠ࠐΈɼఏҊํ. c 2013 Information Processing Society of Japan . ࣔ͢ɽ. 7.

(14) Vol.2013-ARC-206 No.6 2013/7/31. ৘ใॲཧֶձ‫ڀݚ‬ใࠂ IPSJ SIG Technical Report. ΒɼॲཧΛऴྃ͢Δɽ ^ƚĂŐĞϭ. ద༻ྫ ^ƚĂŐĞϰ. ্‫Ͱه‬ड़΂ͨΞϧΰϦζϜΛ‫ʹج‬ɼਤ 14 Λྫʹɼ࣮ࡍ ʹεςʔδ෼ׂΛߦ͏ɽਤத˓ҹ͸ϩδοΫϊʔυΛɼ˘. ^ƚĂŐĞϯ. ҹ͸‫ڥ‬քϊʔυΛද͍ͯ͠Δɽਤ 14(0) ʹɼ‫ڥ‬քϊʔυ d. ^ƚĂŐĞϮ. ͔ΒόοΫΤοδ͕ɼ‫ڥ‬քϊʔυ f ͔Β e ʹ͔͚ͯɼϑΥ ϫʔυΤοδ͕͋Δ৔߹Λࣔ͠ɼ͜ΕΛεςʔδʹ෼ׂ ਤ 12. εςʔδʹ෼ׂ͞Εͨճ࿏. ͢Δɽ. ( 1 ) ʦਤ 14(1)ʧ೚ҙͷ‫ڥ‬քϊʔυͱͯ͠ɼa ΛબΜͩͱ͢ set rst. q. d. Δɽ‫ڥ‬քϊʔυ a ʹ‫͕ܨ‬ΔΤοδΛ୧Γɼ࣍ͷϊʔυ Λ୳ࡧ͢Δɽਖ਼ॱɼ‫ॱٯ‬ͷ྆ํ͔Β࣍ͷϊʔυΛ୧Δ ͱɼ‫ڥ‬քϊʔυ b ͱ c ʹͿ͔ͭΔɽͦͯ͠ɼb Λೖྗ. in. out. in. ଆɼc Λग़ྗଆͷϦετʹ‫ؚ‬Ίɼ୳ࡧ͞ΕΔ‫ڥ‬քϊʔ. out. υ͔Β b Λআ֎͢Δɽ. d q. set rst. ( 2 ) ʦਤ 14(2)ʧ‫ڥ‬քϊʔυ c ͔Β৽ͨͳεςʔδΛ୳ࡧ ͢Δɽc ͔Βɼ(2) ͱಉ༷ʹ୳ࡧ͢Δͱɼ‫ڥ‬քϊʔυ d ͕ೖྗଆɼग़ྗଆ૒ํ͔ΒͿ͔ͭΔɽ͜ͷͨΊɼd Λ. ਤ 13. όοΫΤοδɾϑΥϫʔυΤοδ΁ͷରԠ. ೖग़ྗ྆ํͷϦετʹՃ͑ɼ୳ࡧ͞ΕΔ‫ڥ‬քϊʔυ͔ Β d Λআ֎͢Δɽ. ਤ 13 ্ʹࣔ͢ೋͭͷճ࿏Ͱ͸ɼ੨৭ͷ FF ͱ྘৭ͷ FF. ( 3 ) ʦਤ 14(3)ʧd ͔Β࣍ͷϊʔυʹҠΓɼ(2) ͱಉ༷ʹ‫ڥ‬. ʹ‫·ڬ‬Εͨεςʔδɼ྘৭ͷ FF ͱࢵ৭ͷ FF ʹ‫·ڬ‬Εͨ. քϊʔυΛ୳ࡧ͢Δɽf, g Λೖྗଆʹɼe Λग़ྗଆͷ. εςʔδͷ 2 εςʔδ͕ଘࡏ͠ɼόοΫΤοδ΍ϑΥϫʔ. Ϧετʹ‫ؚ‬Ίɼ୳ࡧ͞ΕΔ‫ڥ‬քϊʔυ͔Β f, g Λআ֎. υΤοδʹΑͬͯ 2 ͭͷεςʔδ͕͍ࠞͬͯ͟Δ͔ͷΑ͏. ͢Δɽಉ༷ʹͯ͠ɼg, h Λग़ྗଆʹ‫ؚ‬ΊΔɽεςʔδ. ʹ‫͑ݟ‬Δɽ. ෼ׂ͕ߦΘΕͨΒɼॲཧΛऴྃ͢Δɽ. ͔͠͠ɼ࣮ࡍʹ͸ɼ͜Ε͸ 1 ͭͷεςʔδͰ͋Γɼ྘৭. Ҏ্ͷΑ͏ͳεςʔδ෼ׂʹΑΓ࡞੒ͨ͠Ϧετ͔Βੜ. ͷ FF ͕͜ͷεςʔδͷೖྗͰ͋Γɼग़ྗͰ΋͋Δɽ྘৭. ੒ͨ͠άϥϑ͕ਤ 14(4) Ͱ͋Δɽਤ 14(0) ͷճ࿏ͱ౳Ձͳ. ͷ FF Λಉεςʔδͷೖྗଆͱग़ྗଆͷ‫ڥ‬քϊʔυ྆ํʹ. ճ࿏Ͱ͋Γɼ࣮ࡍʹεςʔδʹ෼ׂͰ͖Δ͜ͱ͕෼͔Δɽ. ৼΓ෼͚Δ͜ͱͰɼճ࿏શମΛ 1 εςʔδͱͯ͠ɼਖ਼͘͠ εςʔδ෼ׂΛߦ͏͜ͱ͕Ͱ͖Δɽ ΞϧΰϦζϜ ҎԼʹɼεςʔδ෼ׂͷΞϧΰϦζϜΛࣔ͢ɽ. 4.3 ೋ૬ϥονԽ FF ͷεςʔδ୯Ґʹ෼ׂͨ͠άϥϑʹର͠ɼೋ૬ϥο νԽΛߦ͏ɽೋ૬ϥονԽ͸ɼFF ͷεςʔδ಺ͷϩδο. ( 1 ) ೚ҙͷ‫ڥ‬քϊʔυΛ 1 ͭબͿɽ. Ϋʹ‫ٯ‬૬ͷϥονΛૠೖ͠ɼFF ͷεςʔδ୯Ґʹ෼ׂ͠. ( 2 ) ͦͷ‫ڥ‬քϊʔυ͔ΒύεΛ୧Γɼಉεςʔδʹ‫·ؚ‬Ε. ͨάϥϑΛೋ෼͢Δ͜ͱͱ‫͑ݴ‬Δɽ. ΔϊʔυΛ୳ࡧ͢Δɽ୧ͬͨϊʔυ͕ϩδοΫϊʔυ Ͱ͋ͬͨ৔߹͸ɼΤοδͷํ޲ʹؔΘΒͣɼύεΛ୳ ࡧ͢Δɽ. ( 3 ) ‫ڥ‬քϊʔυʹ౸ୡͨ͠৔߹ɼ‫ڥ‬քϊʔυ͕ೖྗଆʹ͋ Δ͔ɼग़ྗଆʹ͋Δ͔Λ‫ͯݟ‬ɼͲͪΒ͔ͷϦετʹՃ. ຬͨ͢΂͖ཁ݅ ೋ૬ϥονԽΛߦ͏ࡍʹຬͨ͢΂͖ཁ݅͸ɼҎԼͷ 2 ͭ ʹΑΓද͞ΕΔɿ. ( 1 ) Ͳͷύε্Λ௨ͬͯ΋ϥονͷૠೖҐஔ͕ඞͣʮ1 ͭ ͚ͩʯଘࡏ͢Δ. ͑Δɽೖྗଆʹ͋ͬͨ৔߹͸ɼ(1) ͷߦఔͰͦͷ‫ڥ‬ք. ೋ૬ϥονԽʹ൐͏ϥονͷૠೖҐஔͷ୳ࡧʹࡍ͠ɼά. ϊʔυ͕બ͹Εͳ͍Α͏ϑϥάΛ෇͚Δɽग़ྗଆʹ. ϥϑͷ༗ޮͳΧοτΛ‫ٻ‬ΊΔΞϧΰϦζϜ͕ͦͷ··ద༻. ͋ͬͨ৔߹͸ɼϑϥά͸͚ͭͳ͍ɽͦͷ‫ޙ‬ɼ‫ڥ‬քϊʔ. Ͱ͖Δ͔ʹࢥ͑Δɽ͔͠͠ɼ༗ޮͳΧοτ͕ਖ਼͍͠ϥον. υ΁୧ͬͨํ޲ͱ͸‫ٯ‬ͷํ޲΁໭Γɼ୳ࡧΛଓ͚Δɽ. ͷૠೖҐஔʹͳΔͱ͸‫ݶ‬Βͳ͍ɽਤ 15 ʹͦͷྫΛࣔ͢ɽ. ( 4 ) શͯͷύεͷ୳ࡧ͕ऴΘͬͨΒɼࠓ·Ͱʹ୧ͬͨϩ δοΫϊʔυΛಉεςʔδ಺ʹ‫·ؚ‬ΕΔϩδοΫϊʔ υͱͯ͠·ͱΊΔɽ. ( 5 ) ʢ1ʣʹ໭Γɼϑϥάͷ͍͍ͭͯͳ͍‫ڥ‬քϊʔυ͔Βผ ͷεςʔδΛ࠶౓୳ࡧ͢Δɽ. ( 6 ) ճ࿏தશͯͷϊʔυʹ͍ͭͯεςʔδ෼ׂ͕ߦΘΕͨ. c 2013 Information Processing Society of Japan . ੨ଠઢ͸ΧοτͷҐஔΛද͍ͯ͠Δɽ ਤ 15 ্ʹࣔ͢ྫ͸Χοτͱͯ͠͸༗ޮͰ͋Δ͕ɼೋ૬ ϥονԽ͸ਖ਼͘͠ߦΘΕ͍ͯͳ͍ɽೖྗଆͷ‫ڥ‬քϊʔυ i1 ͔Βɼग़ྗଆͷ‫ڥ‬քϊʔυ o2 ʹࢸΔύε্ʹ 3 ͭͷΧο τ͕ଘࡏ͢Δɽ͜ͷΧοτ্ʹ‫ٯ‬૬ϥονΛૠೖ͢Δͱɼ ಉύε্ʹ‫ٯ‬૬ϥον͕ෳ਺഑ஔ͞Εɼճ࿏͕ਖ਼͘͠ಈ࡞. 8.

(15) Vol.2013-ARC-206 No.6 2013/7/31. ৘ใॲཧֶձ‫ڀݚ‬ใࠂ IPSJ SIG Technical Report. (0) a. c. f. b. (1). d. 2. 3. 4. 5. 6. 7. 8. 9. 9. 8. 7. 6. 5. 4. 3. 2. 1 9. e. g. d. e. 7. 8. 3. 2. 1. 2. 3. 4. 5. 6. 7. 8. 9. 9. 8. 7. 6. 5. 4. 3. 2. 1. 6. 7. 8. 9. 4. 3. 2. 1. ਤ 16. c. 6 4 1. h. লৡડम௾ਗ慓慤慂. a. 1. ૠೖՕॴʹΑΔϥονͷ࡟‫ݮ‬. ( 2 ) ೋ෼ͨ͠ϩδοΫͷΫϦςΟΧϧɾύε஗Ԇ͕‫ۉ‬౳Ͱ ͋Δ. োৡડ म௾ਗ. b List. in a,b. f. g. ఏҊํࣜͰ͸ɼϥονͷૠೖʹΑΓೋ෼͞Εͨεςʔδ. h. ͷΫϦςΟΧϧɾύε஗ԆʹΑͬͯɼαΠΫϧɾλΠϜ͕. out c. ఆ·ΔɽΫϦςΟΧϧɾύε஗Ԇ͕ΠϯόϥϯεʹͳΔΑ. (2). োলৡ૏্慥அ慫慴. c. a. d. ͏ʹϥονΛૠೖ͢Δͱɼ஗Ԇͷେ͖͍ํͷεςʔδͷΫ ϦςΟΧϧɾύε஗ԆʹΑΓɼαΠΫϧɾλΠϜ͕‫ن‬ఆ͞. e. Εͯ͠·͍ɼαΠΫϧɾλΠϜ͕୹ॖͰ͖ͳ͍ɽ ͦͷͨΊɼೋ෼ͨ͠ϩδοΫͷύε஗Ԇ͕‫ۉ‬౳ʹͳΔΑ f. b List. in a,b. out c. g in c,d. h. ͏ͳద੾ͳҐஔʹϥονΛૠೖ͠ͳ͚Ε͹ͳΒͳ͍ɽ ద༻πʔϧͰ͸ɼϩδοΫͷύε஗ԆΛ Bellman-ford. out d. ๏ [11] Λ༻͍ͯ‫͠ࢉܭ‬ɼద੾ͳϥονͷૠೖҐஔΛ୳ࡧ. (3). ͍ͯ͠Δɽೋ૬ϥονԽʹ͸ɼΫϦςΟΧϧɾύε஗Ԇ c. a. d. ͷ஋Λ‫ʹݩ‬ᮢ஋ΛఆΊΔͨΊɼ࠷௕‫཭ڑ‬ͷ‫ࢉܭ‬Λߦ͏ɽ. e. Bellman-ford ๏͸࠷୹‫཭ڑ‬Λ‫ٻ‬ΊΔΞϧΰϦζϜͰ͋Δ f. b List. in a,b. out c. g. ͕ɼύϥϝʔλʹෛͷ஋ΛऔΔ͜ͱͰ࠷௕‫཭ڑ‬΋‫ٻ‬ΊΔ͜. h. ͱ͕Ͱ͖Δɽ࠷୹‫཭ڑ‬ͷ‫ࢉܭ‬͸‫ޙ‬ͷ TF ‫ݕ‬ग़‫෇ߏػ‬༩ͷϓ ϩηεͰ࢖༻͢Δɽ. in out c,d,f,g d,e,g,h. ( 3 ) ૠೖ͢Δϥονͷ਺͕গͳ͘ͳΔΑ͏ʹ͢Δ. (4). ϥονͷૠೖҐஔʹΑͬͯɼૠೖ͢Δϥονͷ਺͕গͳ a. c. d. b. d. e. f. g. g. h. ͘ͳΔ৔߹͕͋Δɽਤ 16 ͷೋͭͷྫ͸ɼ‫ʹڞ‬ਖ਼͘͠ೋ૬ ϥονԽ͕ߦΘΕ͍ͯΔɽ͔͠͠ɼਤ 16ʢԼʣͷΑ͏ʹɼ ύεͷ෼‫ذ‬ͷखલʹϥονΛஔ͘͜ͱʹΑΓɼϥονͷ਺ Λ 2 ͔Β 1 ʹ‫ݮ‬Β͢͜ͱ͕Ͱ͖Δɽ ͜ͷͨΊɼ୳ࡧͨ͠ૠೖҐஔͷީิ͔Βɼૠೖ͢Δϥο. ਤ 14. νͷ਺͕গͳ͍΋ͷΛબͿɽ ୳ࡧۭؒͷ࡟‫ݮ‬. εςʔδ෼ׂͷྲྀΕ. ઌʹड़΂ͨ৚͕݅ຬͨ͞Ε͍ͯ͑͢͞Ε͹ɼೋ૬ϥον. i1. o1. i2. ͱɼ୳ࡧۭ͕ؒ๲େʹͳΔɽ ຊπʔϧͰ͸ɼύε஗ԆʹΑΔૠೖҐஔͷࣗ༝౓ͷҧ͍. o2. i1. Խ͸ਖ਼͘͠ߦΘΕΔ͕ɼશͯͷૠೖҐஔΛ୳ࡧ͢ΔͱͳΔ. ʹண໨͠ɼ୳ࡧۭؒΛ཈͑ΔɽҎԼͰ͸ਤ 17 Λ༻͍ͯɼ o1. ͜ͷ͜ͱΛઆ໌͢ΔɽϩδοΫϊʔυͷ্ʹ෇ਵ͢Δ਺ࣈ ͸ɼೖྗଆͷ‫ڥ‬քϊʔυ͔Βͷ࠷௕‫཭ڑ‬Λ͍ࣔͯ͠Δɽ. i2. o2. ਤ 15. ೋ૬ϥονԽͷ࣮ࡍ. ͠ͳ͍ɽ. ઌʹड़΂੍ͨ໿ʹΑΓɼΫϦςΟΧϧɾύε্ͷϥον ͷૠೖҐஔʢਤ 17 ্ʣ͸ɼࣗ༝౓͕গͳ͍ɽ͜Εʹର͠ɼ γϣʔτɾύε্ͷϥονͷૠೖҐஔʢਤ 17 Լʣ͸ɼೋ෼ ͨ͠εςʔδͷΫϦςΟΧϧɾύε஗ԆΛ௒͑ͳ͍Α͏ʹ. ճ࿏͕ਖ਼͘͠ಈ࡞͢ΔͨΊʹ͸ɼਤ 15 Լʹࣔ͢ྫͷΑ. ෼ׂ͢Ε͹Α͘ɼࣗ༝౓͸େ͖͍ɽΫϦςΟΧϧɾύε஗. ͏ʹɼͲͷύεΛ௨ͬͯ΋ɼΧοτ͕Ұ͚ͭͩଘࡏ͢ΔΑ. ԆΑΓγϣʔτɾύε஗Ԇ͕খ͍͞΄Ͳɼࣗ༝౓͸େ͖͘. ͏ʹɼૠೖҐஔΛఆΊͳ͚Ε͹ͳΒͳ͍ɽ. ͳΔɽ. c 2013 Information Processing Society of Japan . 9.

(16) Vol.2013-ARC-206 No.6 2013/7/31. ৘ใॲཧֶձ‫ڀݚ‬ใࠂ IPSJ SIG Technical Report 1. 2. 1. 3. 2. ਤ 17. 4. 3. 5. 4. 6. 5. 7. 8. 9 9. 6. 1. 2. 3. 4. 5. 6. 7. 8. 9. 9. 8. 7. 6. 5. 4. 3. 2. 1. 1. 2. 3. 4. 5. 6. 7. 8. 9. 9. 8. 7. 6. 5. 4. 3. 2. 1. ਤ 19. ύε஗ԆʹΑΔૠೖՕॴͷࣗ༝౓ͷҧ͍ 慏慏ऊ慲઩慫慠‫ؼ‬. 1. 2. 3. 4. 5. 6. 7. 8. 1. 2. 3. 4. 5. 6. 7. 8. 9. 9. i1 i2 慙慩慙慩懙慏慏慥োो慴慢‫ؼ‬. 8. o1. o2. 9. 9. ಉ࣌ʹબΜͩ৔߹. ͳ͓ɼ୳ࡧͷࡍʹೖྗଆͱग़ྗଆͷ‫ڥ‬քϊʔυΛಉ࣌ʹ બͿͷ͸ಘࡦͰ͸ͳ͍ɽਤ 19 ͷΑ͏ʹɼ‫࠷͕཭ڑ‬େͷೖ ྗଆɼग़ྗଆͷ‫ڥ‬քϊʔυΛબΜͰ΋ɼͦͷؒʹύε͕͋ Δͱ͸‫ݶ‬Βͳ͍͔ΒͰ͋Δɽ. ঱भঃ憔慷ພो慴. ΞϧΰϦζϜ. 1. 2. 3. 4. 5. 6. 7. 8. 1. 2. 3. 4. 5. 6. 7. 8. 9. 9. i1 i2. 8. o1. o2. ͜Ε·Ͱʹड़΂ͨ࿦఺Λ౿·͑ɼҎԼʹࣔ͢ΞϧΰϦζ ϜʹΑΓɼೋ૬ϥονԽΛߦ͏ɿ. ( 1 ) ‫ڥ‬քϊʔυ͕ FF Ͱ͋Δ৔߹ʹɼਖ਼૬ϥον΁ͱม‫׵‬ ͢Δɽ. 慏慏ऊ慲઩慫慠‫ؼ‬. 9 8. i1 i2. 1. 2. 3. 4. 5. 6. 7. 8. 9. 9. 8. 7. 6. 5. 4. 3. 2. 1. 1. 2. 3. 4. 5. 6. 7. 8. 8. 7. 6. 5. 4. 3. 2. 1. 8. i1 i2. o1. Λߦ͍ɼೖྗଆͷ‫ڥ‬քϊʔυ͔Β֤ϩδοΫϊʔυʹ քϊʔυ͔Βೖྗଆͷ‫ڥ‬քϊʔυ΁ͱ‫࠷ʹॱٯ‬௕‫཭ڑ‬. 1. 2. 3. 4. 5. 6. 7. 8. 9. 9. 8. 7. 6. 5. 4. 3. 2. 1. 1. 2. 3. 4. 5. 6. 7. 8. 8. 7. 6. 5. 4. 3. 2. 1. ਤ 18. ( 2 ) ೖྗଆͷ‫ڥ‬քϊʔυ͔Βग़ྗଆͷ‫ڥ‬քϊʔυ΁ͱ୳ࡧ ࢸΔύεͷ࠷௕‫཭ڑ‬Λ‫͢ࢉܭ‬Δɽಉ༷ʹɼग़ྗଆͷ‫ڥ‬. o2. 慙慩慙慩懙慏慏慥োो慠慬‫ؼ‬. ઃम慏ोऊ慲. 9. 8. 9. 8. 9. Λ‫͢ࢉܭ‬Δɽ o1. o2. ୳ࡧ࿙Εͷ๷ࢭ. ( 3 ) ‫ڥ‬քϊʔυͷ࣋ͭ࠷௕‫཭ڑ‬ͷ࠷େ஋ΛɼεςʔδͷΫϦ ςΟΧϧɾύε஗Ԇ dmax ͱ͠ɼᮢ஋ dth = 1/2dmax +1 Λ‫ٻ‬ΊΔɽͦͯ͠ɼdth Ҏ্ͷ࠷௕‫཭ڑ‬Λ࣋ͭϊʔυ͔ Βग़ΔΤοδΛϥονͷૠೖҐஔީิ͔Βআ֎͢Δɽ. ͜ͷͨΊɼΫϦςΟΧϧɾύεͱ͍ͬͨɼ஗Ԇͷେ͖͍. Ҏ্·ͰͷߦఔΛࡁ·ͤͨάϥϑΛਤ 20 ʹࣔ͢ɽҎԼɼ. ύε͔ΒॱʹϥονͷૠೖҐஔΛఆΊɼϥονͷૠೖҐஔ. ਤ 20 Λ‫ʹج‬ૠೖҐஔΛܾఆ͢ΔΞϧΰϦζϜΛઆ໌͢Δɽ. Λ͋Δఔ౓‫ݶ‬ఆͨ͠‫ޙ‬ɼγϣʔτɾύε্ͷϥονͷૠೖ. ( 4 ) ʦਤ 20(a)ʧೖྗଆͷ‫ڥ‬քϊʔυͱग़ྗଆͷ‫ڥ‬քϊʔυ. ҐஔΛఆΊΔ͜ͱͰɼ୳ࡧۭؒΛ཈͑Δ͜ͱ͕ՄೳͱͳΔɽ. Λɼ࠷௕‫཭ڑ‬ͷେ͖͍ॱʹΦʔμϦϯά͢Δɽ࠷௕‫ڑ‬. ୳ࡧ࿙Εͷ๷ࢭ. ཭ͷେ͖ͳ‫ڥ‬քϊʔυ͔Βॱʹ 1 ͭબͿɽύε্ͷૠ. ૠೖҐஔΛܾఆ͢Δࡍʹɼग़ྗଆͷ‫ڥ‬քϊʔυ͔Βૠೖ. ೖҐஔΛ୳ࡧ͠ɼରԠ͢ΔՕॴͷΤοδΛ 1 ͭબͿɽ. ҐஔΛ୳ࡧ͚ͨͩ͠Ͱ͸ɼϥονͷૠೖҐஔʹ࿙Ε͕ൃੜ. ( 5 ) ʦਤ 20(b)ʧͦͷΤοδ͔Βೖྗଆɼग़ྗଆ૒ํʹର. ͢Δ৔߹͕͋ΔɽҎԼͰ͸ਤ 18 Λ༻͍ͯɼ͜ͷ͜ͱΛઆ. ͯ͠୳ࡧΛߦ͍ɼϥονΛૠೖ͢Δඞཁͷͳ͍Τοδ. ໌͢Δɽ. Λআ֎͢Δɽ͜ͷ୳ࡧ࣌ʹͿ͔ͭΔ‫ڥ‬քϊʔυ͸‫ʹط‬. ਤ 18 ্͸ɼग़ྗଆͷ‫ڥ‬քϊʔυ͔ΒͷΈ୳ࡧͨ͠৔߹ Λද͍ͯ͠Δɽ‫ڥ‬քϊʔυ o1 ʹࢸΔύεΛ୳ࡧ͠ɼ੨ଠ. ϥον͕ૠೖ͞Ε͍ͯΔύεΛ࣋ͭɽͦͷͨΊɼ୳ࡧ ީิ͔ΒऔΓআ͘ɽ. ઢͷҐஔʹ͋ΔΤοδΛૠೖҐஔͱͯ͠બΜͩͱ͢Δɽͦ. ( 6 ) ʦਤ 20(c)ʧ୳ࡧީิʹ࢒͍ͬͯΔ‫ڥ‬քϊʔυͰ஗Ԇͷ. ͷΤοδ͔Β͜ΕҎ্ϥονΛૠೖ͢Δඞཁͷͳ͍ύεΛ. େ͖͍΋ͷΛબ୒͠ɼ(4)-(5) Λ‫܁‬Γฦ͢ɽશͯͷΤο. ୳ࡧ͠ɼީิ͔Βআ֎͢Δɽ࣍ʹɼ‫ڥ‬քϊʔυ o2 ʹࢸΔ. δʹϥονΛૠೖ͢Δඞཁ͕ͳ͘ͳͬͨΒɼ୳ࡧΛऴ. ύεΛ୳ࡧ͢Δͱɼύε্ͷશͯͷΤοδ͕ϥονΛೖΕ. ྃ͢Δɽ. Δඞཁ͕ͳ͍͜ͱ͕෼͔Γɼ୳ࡧ͕ऴྃͯ͠͠·͏ɽ͔͠. ( 7 ) (4)-(6) Λ‫܁‬Γฦ͠ɼશͯͷૠೖީิΛ্͛ͨͷͪɼϥο. ͠ɼૠೖ͢΂͖‫ॴݸ‬͸࢒ଘ͓ͯ͠Γɼ͜ͷ··Ͱ͸ਖ਼͘͠. νͷҰ൪গͳ͍΋ͷΛબͿɽͦͷૠೖՕॴͷΤοδʹ. ೋ૬ϥονԽΛߦ͑ͳ͍ɽ. ‫ٯ‬૬ͷϥονΛද͢‫ڥ‬քϊʔυΛૠೖ͠ɼάϥϑΛ 2. ͜ΕΛ๷͙ͨΊʹɼग़ྗଆͷ‫ڥ‬քϊʔυ͔Βͷ࠷௕‫཭ڑ‬ ΋‫ٻ‬Ίɼೖྗଆͷ‫ڥ‬քϊʔυ͔Β΋ύεΛ୳ࡧ͢Δɽਤ 18 Լʹ͜ͷ༷ࢠΛࣔ͢ɽϩδοΫϊʔυԼʹ෇ਵ͢Δ਺ࣈ. ෼͢Δɽ Ҏ্ͷߦఔͰɼೋ૬ϥονԽΛऴྃ͢ΔɽҎ߱ͷߦఔͰ ͸ (7) Ͱ࡞੒ͨ͠άϥϑΛ༻͍Δɽ. ͸ɼग़ྗଆͷ‫ڥ‬քϊʔυ͔Βͷ࠷௕‫཭ڑ‬Λ͍ࣔͯ͠Δɽ‫ڥ‬ քϊʔυ o1 ʹࢸΔύεΛ୳ࡧ͠ɼީิΛআ֎ͨ࣍͠ʹɼ‫ڥ‬ քϊʔυ i1 ͔Βग़ΔύεΛ୳ࡧ͢Δɽ͜ͷΑ͏ʹ͢Δ͜ͱ Ͱɼૠೖ࿙ΕΛճආ͢Δ͜ͱ͕Ͱ͖Δɽ. c 2013 Information Processing Society of Japan . 4.4 TF ‫ݕ‬ग़‫ߏػ‬ͷ෇༩ ೋ૬ϥονԽΛߦͬͨάϥϑʹର͠ɼTF ‫ݕ‬ग़‫ߏػ‬Λ෇ ༩͢ΔɽͦͷͨΊʹɼRazor ͷૠೖ΍ɼ஗Ԇૉࢠͷૠೖɼ. 10.

(17) Vol.2013-ARC-206 No.6 2013/7/31. ৘ใॲཧֶձ‫ڀݚ‬ใࠂ IPSJ SIG Technical Report (1) 9. 1. 2. 3. 4. 5. 6. 7. 8. 9. 9. 8. 7. 6. 5. 4. 3. 2. 1. 1. 2. 3. 4. 7. 6. 5. 8. 8. 7. 8 1. 1. 5. 6. 7. 2. 1. ( 1 ) ೖྗଆͷ‫ڥ‬քϊʔυ͔Βɼ֤ϊʔυͷ࠷୹‫ܦ‬࿏ dmin 9. ͱ࠷௕‫ܘ‬࿏ dmax Λ Bellman-ford ๏ʹΑΓ‫ٻ‬ΊΔɽ ʦਤ 21(1)ʧ֤ϊʔυͷ্෦ࠨଆ͕ dmin ɼӈଆ͕ dmax. 8. Λද͢ɽ. 6. ( 2 ) ग़ྗଆͷ‫ڥ‬քϊʔυͷதͰ࠷௕ͳ‫཭ڑ‬ΛΫϦςΟΧ. search. (2) 9. ௾ਗ. 1. 2. 3. 4. 5. 6. 7. 8. 9. 9. 8. 7. 6. 5. 4. 3. 2. 1. 1. 2. 3. 4. 8. 8. 7. 6. 5. 1. 8. 7. 1. 5. 6. 7. 2. 1. ϧɾύε஗Ԇ dcp ͱ͠ɼ͜ΕΛ‫ʹج‬ᮢ஋Λ‫ٻ‬ΊΔɽ. 9 ௾ਗ. 8. ௾ਗ. 6. (3) 9. 1. 2. 3. 4. 5. 6. 7. 8. 9. 9. 8. 7. 6. 5. 4. 3. 2. 1. 1. 2. 3. 4. 7. 6. 5. 8. 8. 7. 8 1. 1. 5. 6. 7. 2. 1. 9. 8. 6. ʦਤ 21(1)ʧ͜ͷྫͰ͸ɼdcp = 4 Ͱ͋Δ͔Βɼdrazor = 2 Ҏ্ͷϥονΛ Razor ʹม͑ɼdth = 3 ҎԼͷγϣʔ τɾύεʹ஗ԆΛૠೖ͢Δ͜ͱͱ͢Δɽ. ( 3 ) ग़ྗଆͷ‫ڥ‬քϊʔυΛ೚ҙʹҰͭબͿɽ͜ͷ‫ڥ‬քϊʔ υͷ࠷௕‫ܘ‬࿏ dmax Λ‫ݟ‬Δ͜ͱͰɼRazor ʹมߋ͢ Δ͔ΛܾΊΔɽRazor ʹมߋ͢Δඞཁ͕͋ͬͨ৔߹ɼ. Shadow Latch Λ෇༩͠ɼखલͷϊʔυ͔ΒΤοδΛ ͭͳ͙ɽͦͯ͠ɼೖྗଆͷ‫ڥ‬քϊʔυʹ޲͔ͬͯɼਂ. ਤ 20. ೋ૬ϥονԽͷྲྀΕ. ͞ D Λ‫͢ࢉܭ‬Δɽ ʦਤ 21(2)ʧબ͹Εͨ‫ڥ‬քϊʔυΛᒵ৭Ͱࣔ͢ɽ͜͜. ήʔτͷೋॏԽͱ͍ͬͨાஔΛߦ͏ඞཁ͕͋Δɽ. Ͱ͸ɼdmax > drazor Ͱ͋Δ͔ΒɼRazor ʹมߋ͕ඞ ཁͰ͋ΔͨΊɼShadow Latch Λ෇༩͢Δɽ. ຬͨ͢΂͖ཁ݅. TF ‫ݕ‬ग़‫ߏػ‬Λ෇༩͢ΔͨΊʹຬͨ͢΂͖ཁ݅͸ɼҎԼ. ( 4 ) ग़ྗଆͷ‫ڥ‬քϊʔυ͔Βೖྗଆͷ‫ڥ‬քϊʔυ΁޲͔ͬ ͯɼਂ͞༏ઌͰϩδοΫϊʔυΛ୳ࡧ͠ҰͭબͿɽͦ. ͷ 3 ͭͰ͋Δɿ. ͷϩδοΫϊʔυ͕γϣʔτɾύεΛ‫ؚ‬Ή͔Ͳ͏͔. ( 1 ) TF ΛҾ͖‫͢͜ى‬Մೳੑͷ͋Δύε͕ଘࡏ͢Δग़ྗଆ. Λ൑அ͢ΔɽϩδοΫϊʔυͷ࠷খ஗Ԇ dmin ͱਂ͞. ͷϥονΛ Razor Latch ʹมߋ͢Δ. Dself ͷ࿨͔Β 1 ΛҾ͍ͨ΋ͷ͕ɼdth ΑΓ΋খ͚͞. ҰൠʹɼTF ‫ݕ‬ग़‫ߏػ‬͸ɼΫϦςΟΧϧɾύεͷ஗ԆΛ‫ݕ‬ग़. Ε͹ͦͷϩδοΫϊʔυ͸γϣʔτɾύεΛ‫ؚ‬ΜͰ͍. ‫ݶ‬քͱͯ͠ఆΊΔɽ‫ݕ‬ग़΢Οϯυ΢෯Λ W ɼεςʔδͷΫ. ΔɽγϣʔτɾύεΛ‫ؚ‬ΜͰ͍ͨ৔߹ɼͦͷϩδοΫ. ϦςΟΧϧɾύε஗ԆΛ dcp ͱ͢ΔͱɼRazor Latch ͷมߋ. ϊʔυΛೋॏԽ͢Δɽ. Λ͢Δ͔ΛܾΊΔᮢ஋ drazor ͸ɼdcp −W Ͱද͞ΕΔɽग़ྗ. ʦਤ 21(3)ʧ͜͜Ͱ͸ɼϩδοΫϊʔυ a ͕બ͹ΕΔɽ. ଆͷϥονʹࢸΔύεͷ࠷େ஗ԆΛ dmax (0 < dmax ≤ dcp ). ࠓɼϩδοΫϊʔυ a Ͱ͸ɼdmin +Dself −1 = 2 < dth. ͱ͢ΔͱɼRazor ͷૠೖ৚݅͸ɼdmax ≥ drazor Ͱද͞ΕΔɽ. Ͱ͋Δ͔ΒɼγϣʔτɾύεΛ‫ؚ‬ΜͰ͍Δɽ͜ͷͨΊɼ. ( 2 ) ‫ݕ‬ग़΢Οϯυ΢෯Λ௒͑Δ஗ԆʹͳΔΑ͏ʹɼγϣʔ. ϩδοΫϊʔυ a ΛೋॏԽ͢Δɽ. τɾύεʹ஗ԆΛૠೖ͢Δ. ( 5 ) ೋॏԽͨ͠ϩδοΫϊʔυʹࢸΔύεͷத͔Βɼγϣʔ. ‫ݕ‬ग़΢Οϯυ΢Λ֬อ͢ΔͨΊʹɼγϣʔτɾύεͷ஗. τɾύεΛ୳ࡧ͠ɼ஗ԆΛૠೖ͢Δɽೖྗଆʹ޲͔ͬ. ԆΛ‫ݕ‬ग़΢Οϯυ΢෯ W Ҏ্ʹ͢Δඞཁ͕͋Δɽ͜ͷͨ. ͯϊʔυΛ 1 ͭ෼୧Δɽͦͷϊʔυͷ࠷େ஗Ԇ dmax. Ίɼ஗ԆΛೖΕΔ͔ΛܾΊΔᮢ஋ dth ͸ɼdth ≥ W Ͱද. ͱɼೋॏԽͨ͠ϩδοΫϊʔυͷਂ͞ Dprev ͷ࿨͕ɼ. ͞ΕΔɽγϣʔτɾύεͷ஗ԆΛ dsp ͱ͢Δͱɼ‫ݕ‬ग़΢Ο. dth ΑΓখ͚͞Ε͹ɼͦͷΤοδ͸γϣʔτɾύεͰ͋. ϯυ΢Λ֬อ͢ΔͨΊʹɼdsp ≤ dth ͷύεʹର͠ɼ࠷௿. Δ͜ͱ͕෼͔ΔɽγϣʔτɾύεͰ͋Δ͜ͱ͕෼͔ͬ. dth − dsp ͷ஗ԆΛૠೖ͢Δඞཁ͕͋Δɽ. ͨΒɼdth ͔Βɼ୧ͬͨϊʔυͷਂ͞ Dself ΛҾ͍ͨ. ( 3 ) ೋॏԽήʔτͷ਺͕Ͱ͖Δ͚ͩগͳ͘ͳΔΑ͏ʹ͢Δ. ਺͚ͩɼೋॏԽͨ͠Τοδʹ஗ԆΛૠೖ͢Δɽ. ճ࿏໘ੵͷΦʔόʔϔουΛ཈͑ΔͨΊʹ, Ͱ͖Δ͚ͩ. ʦਤ 21(4)ʧϩδοΫϊʔυ a ͔Βೖྗଆʹ޲͔ͬͯ. ೋॏԽ͢ΔήʔτΛগͳ͍ͨ͘͠. ೖྗଆʹ஗ԆૉࢠΛૠ. ϊʔυΛ 1 ͭ෼୧ΔͱɼϩδοΫϊʔυ bɼ c ͕‫ͭݟ‬. ೖͨ͠৔߹ɼ஗Ԇ͕ૠೖ͞Ε͍ͯΔύεͱ͞Ε͍ͯͳ͍. ͔Δɽ͜ͷͦΕͧΕʹର͠ɼdmax + Dprev Λ‫͢ࢉܭ‬. ύεΛ෼͚ΔͨΊʹ͸ɼ஗ԆૉࢠҎ߱ʹଘࡏ͢Δϩδο. ΔͱɼϩδοΫϊʔυ a − b ؒͷΤοδ͕γϣʔτɾ. ΫϊʔυશͯΛೋॏԽ͠ͳ͚Ε͹ͳΒͳ͍ɽ͜ͷͨΊɼε. ύεͰ͋ΓɼϩδοΫϊʔυ a − c ؒͷΤοδ͕ΫϦ. ςʔδͷग़ྗଆʹͰ͖Δ͚͍ͩۙͱ͜Ζʹ஗ԆૉࢠΛૠೖ. ςΟΧϧɾύεͰ͋Δ͜ͱ͕෼͔ΔɽϩδοΫϊʔυ. ͢Δ͜ͱͰճ࿏໘ੵͷ૿ՃΛܰ‫͢ݮ‬Δ.. b ͷਂ͞ Dself Λ dth ͔ΒҾ͍ͨ஋͸ 1 ͳͷͰɼϩδο. ΞϧΰϦζϜ. Ϋϊʔυ a − b ؒͷෳ੡ͨ͠Τοδʹ஗ԆΛ 1 ͭૠೖ. ҎԼɼਤ 21ɼਤ 22 ͷάϥϑΛ‫ʹج‬ɼTF ‫ݕ‬ग़‫ߏػ‬Λ෇ ༩͢ΔΞϧΰϦζϜΛઆ໌͢Δɽ. c 2013 Information Processing Society of Japan . ͢Δɽ. ( 6 ) ஗ԆૠೖΛߦͬͨύε্ͷϊʔυ͸୳ࡧ͔Βআ֎ͯ͠ɼ. 11.

(18) Vol.2013-ARC-206 No.6 2013/7/31. ৘ใॲཧֶձ‫ڀݚ‬ใࠂ IPSJ SIG Technical Report. ࣍ͷϩδοΫϊʔυΛ୳ࡧ͠ɼ(4)-(6) Λ‫܁‬Γฦ͢ɽͦ. (1). ͯ͠ɼ͜ͷϩδοΫϊʔυ͕ೋॏԽͷඞཁ͕͋Γɼલ. 0|0. 1|1. 2|4. 嵥. 嵤. ʹೋॏԽ͞ΕͨϩδοΫϊʔυͱͷΤοδ͕ଘࡏ͢Δ ৔߹͸ɼͦͷΤοδΛೋॏԽͨ͠ϩδοΫϊʔυʹ‫ܨ‬. 4. 1|3. 0|0. ͔͗͑Δɽ. 嵦. ʦਤ 22(5)ʧઌఔϩδοΫϊʔυ b ͸஗ԆૠೖΛߦͬͨ 1|2. 0|0. ͷͰɼϩδοΫϊʔυ c ΁Ҡಈ͢Δɽͦͯ͠ɼϩδο. 嵧. Ϋϊʔυ c ʹର͠ɼೋॏԽͱ஗ԆૠೖΛߦ͏ɽϩδο Ϋϊʔυ c ͸ϩδοΫϊʔυ a ͷೋॏԽͨ͠ํͱ‫ܨ‬. 0|0. 1|1 嵨. 0|0. 1|1. ͕͍ͬͯΔͷͰɼc ͷೋॏԽͷࡍʹɼͦͷΤοδΛϩ. 3. δοΫϊʔυ c ͷೋॏԽͨ͠ଆʹ‫͔͑͗ܨ‬Δɽ. ( 7 ) (4) Ͱड़΂ͨγϣʔτɾύεͷࣜΛຬͨ͞ͳ͍ϊʔυʹ. (2). dmax > drazor 2|4. ౸ୡͨ͠৔߹ɼ͜ΕҎ߱ͷύεͷ୳ࡧΛ΍Ίɼ(3) Ͱબ. 2. 嵥. 嵤. Μͩ‫ڥ‬քϊʔυ͔Βͷύεʹର͢ΔॲཧΛऴྃ͢Δɽ. D=2. D=2. D=1. ʦਤ 22(6)ʧϩδοΫϊʔυ d ΁ͱҠಈ͢Δɽϩδο. 0|0. Ϋϊʔυ d ʹ͓͍ͯ͸ɼdmin + Dself − 1 = 3 ≥ dth Ͱ͋Δ͔Βɼ͜ͷϊʔυʹ͸γϣʔτɾύε͕ଘࡏ͠. 1|3. 2. 嵦. D=2. D=2. 0|0. ͳ͍͜ͱ͕෼͔Δɽ͜ͷͨΊɼϩδοΫϊʔυ e ΁ͷ ୳ࡧΛ΍ΊΔɽ. 1|2. 3. 嵧. D=3. D=3. 0|0. ( 8 ) ʦਤ 22(7)ʧผͷ‫ڥ‬քϊʔυΛબͼɼ(3) ͷߦఔ͔Β࠶౓. 3. 4. 1|1 嵨. D=4. D=4. 0|0. 1|1. 2. 嵥. 嵤. Θͬͨάϥϑ͸ਤ 22(8) Ͱ͋Δɽਤ͔ΒΘ͔Δ௨ΓɼMain. D=2. D=2. D=1. Latch ʹࢸΔύεʹ͸஗Ԇ͸ૠೖ͞Ε͓ͯΒͣɼShadow. 0|0. Latch ʹࢸΔύεʹ͸શͯ஗Ԇ͕ૠೖ͞Εɼ࠷খ஗Ԇ੍໿. 2. 嵦. D=2. D=2. ΍Γ௚͢ɽલͷߦఔͰೋॏԽ΍஗ԆૠೖΛߦͬͨϊʔ υʹରͯ͠΋ɼ࠶౓ಉ༷ͷॲཧΛߦ͏ɽ. (3). Ҏ্ͷΞϧΰϦζϜͰɼશͯͷύεʹର͠ɼTF ‫ݕ‬ग़‫ػ‬ ߏΛ෇༩͢Δɽਤ 21(1) ʹର͠ɼTF ‫ݕ‬ग़‫ߏػ‬Λ෇༩͠ऴ. Λຬ͍ͨͯ͠Δ͜ͱ͕෼͔Δɽ. dmin + Dself ± 1 = 2 < dth. 5. ͓ΘΓʹ ۙ೥໰୊ͱͳΓͭͭ͋Δ LSI ͷ͹Β͖ͭ΁ͷରࡦͱ͠. 嵧. D=3. D=3. 3. 4. 1|1 嵨. D=4. D=4. 0|0. 1|1. 2. ଘͷख๏Ͱ͸੒͠ಘͳ͔ͬͨɼΫϦςΟΧϧɾύεΑΓ͸. 嵥. D=2. D=2. Δ͔ʹ୹͍࣮ޮ஗Ԇʹ‫ͮ͘ج‬αΠΫϧɾλΠϜΛ‫ن‬ఆͰ͖. 0|0. ΔΫϩοΩϯάํࣜͰ͋Γɼೋ૬ϥονํࣜʹλΠϛϯ. 2. 嵦. άɾϑΥʔϧτ‫ݕ‬ग़ٕज़Λ૊Έ߹ΘͤΔ͜ͱʹΑΓ࣮‫͞ݱ‬. D=2. D=2. ΕΔɽຊߘͰ͸ɼ͜ͷख๏Λ୯૬ FF ํࣜͷ൚༻ͳճ࿏ʹ. 0|0. ͯɼλΠϛϯάɾϑΥʔϧτͷ‫ݕ‬ग़/ճ෮ٕज़͕͋Δɽզʑ ͸Ҏલɼ͜ͷٕज़Λ͞Βʹਪ͠ਐΊͨख๏ͱͯ͠ɼಈతλ ͍ͯ͠Δɽ͜Ε͸ೖྗ͹Β͖ͭʹண໨͢Δ͜ͱʹΑΓɼ‫ط‬. (4). dmax + Dprev = 2 < dth. 1|2. 3. 嵧 D=3. ड़΂ͨ.. 0|0. ग़ͨ͠άϥϑʹ‫͍ͯͮج‬ɼೋ૬ϥονํࣜ΁ͷม‫ͱ׵‬ɼλ ΠϛϯάɾϑΥʔϧτ‫ݕ‬ग़‫ߏػ‬ͷ෇༩Λߦ͏ͱ͍ͬͨϓϩ. 嵤. 4. D=1 1|3. D=3. ͠ɼͦͷάϥϑΛεςʔδ͝ͱʹ੾Γग़͢ɽͦͷ‫ޙ‬ɼ੾Γ. 2|4. dth ± Dself = 1଻. ରͯࣗ͠ಈతʹద༻͢ΔͨΊͷπʔϧͷ࣮૷ํ๏ʹ͍ͭͯ ద༻ࣗಈԽπʔϧ͸ɼEDIF ‫ࣜܗ‬ͷճ࿏Λάϥϑʹม‫׵‬. 4. 1|2. 3. 0|0. 2|4. 1|3. 0|0. ΠϜɾϘϩʔΠϯάΛՄೳʹ͢ΔΫϩοΩϯάํࣜΛఏҊ. 4. 4. 1|1 嵨. D=4. D=4 憏懑憣. ਤ 21. 崴੎৲憏懑憣. dmax + Dprev = 4 > dth 3. ೚భಞ৕. 嵕嵫嵤嵧嵲嵺崢嵎嵤嵷嵦嵫. TF ‫ݕ‬ग़෇༩ͷྲྀΕ (1-4). ηεΛ‫ܦ‬Δɽ֤ϓϩηεͷ࢓༷ɼͦΕΛຬͨͨ͢Ίͷཁ݅ Λྻ‫͠ڍ‬ɼಈ࡞Λ࣮‫͢ݱ‬ΔΞϧΰϦζϜΛड़΂ͨɽ. c 2013 Information Processing Society of Japan . 12.

(19) Vol.2013-ARC-206 No.6 2013/7/31. ৘ใॲཧֶձ‫ڀݚ‬ใࠂ IPSJ SIG Technical Report. ࠓ‫ޙ‬͸͜ͷπʔϧΛ༻͍ͯఏҊख๏Λద༻ͨ͠ FPU ΍. (5) 0|0. 1|1 嵥. 2 D=2 0|0. D=2 dmax + Dprev = 2 < dth. 2. 2|4. 2|4. 嵤. 4. D=1 dmin + Dself ± 1 = 2 < dth. 嵦. ࢀߟจ‫ݙ‬. 1|2. 1|3. 3. 嵧. 3. D=3. D=3. 0|0. 0|0. dth ± Dself = 1଻. ँࣙ ຊ‫ڀݚ‬ͷҰ෦͸ɼจ෦ՊֶলՊֶ‫ڀݚ‬අิॿۚ. No. 23300013 ʹΑΔ.. 1|3 D=2. D=2. ϓϩηοαͳͲΛ࣮૷ͯ͠ධՁ͍ͯ͘͠༧ఆͰ͋Δ.. dmax + Dprev = 4 > dth. [1] [2]. 4. 1|1 嵨. D=4. D=4. 0|0. 1|1. 2. 嵥. 嵤. D=2. D=2. D=1. [3]. (6) 2|4. 0|0. [4]. 1|3. 2. 嵦. D=2. D=2. 0|0. 1|2. 3. 嵧. D=3. D=3. 0|0. 4. 3. [5]. dmin + Dself ± 1 = 3 Ӎ dth. 4. 1|1 嵨. D=4. D=4. 0|0. 1|1. 2|4. 嵥. 嵤. (7). 0|0. dmax + Dprev = 1 < dth. 1. 1|3 D=1 dmax Ӎ dth. 0|0. [7]. 1|2. 2. 嵧. D=2. D=2. 0|0. 嵦. dth ± Dself = 2଻. D=1. [6] 4. 3. 1|1 嵨. D=3. D=3. 3 dmax + Dprev = 3 Ӎ dth. [8]. [9] (8). [10] 嵥. 嵤. [11]. 嵦. Ԭా݈Ұɿूੵճ࿏ʹ͓͚Δੑೳ͹Β͖ͭղੳʹؔ͢Δ ‫ڀݚ‬ɼത࢜࿦จɼ‫౎ژ‬େֶ (2003). ฏຊढ़࿠ɼɹ஛಺ܿɼ੢ాজஉɿMOS τϥϯδελͷ εέʔϦϯάʹ൐͏ಛੑ͹Β͖ͭɼిࢠ৘ใ௨৴ֶձࢽɼ Vol. 92, No. 6 (2009). D.Ernst, N.Kim, S.Das, S.Pant, T.Pham, R.Rao, C.Ziesler, D.Blaauw, T.Austin and T.Mudge: Razor: A Low-Power Pipeline Based on Circuit-Level Timing Speculation, Int’l Symp. on Microarchitecture (MICRO), pp. 7–18 (2003). Blaauw, D., Kalaiselvan, S., Lai, K., Ma, W.-H., Pant, S., Tokunaga, C., Das, S. and Bull, D.: Razor II: In Situ Error Detection and Correction for PVT and SER Tolerance, Int’l Symp. on Solid-State Circuits Conference (ISSCC) (2008). Bull, D., Das, S., Shivshankar, K., Dasika, G., Flautner, K. and Blaauw, D.: A power-eﬃcient 32b ARM ISA processor using timing-error detection and correction for transient-error tolerance and adaptation to PVT variation, Solid-State Circuits Conference Digest of Technical Papers (ISSCC), 2010 IEEE International, pp. 284 –285 (online), DOI: 10.1109/ISSCC.2010.5433919 (2010). Mallik, A., Cosgrove, J., Dick, R. P., Memik, G. and Dinda, P.: PICSEL: Measuring User-Perceived Performance to Control Dynamic Frequency Scaling, Int’l Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pp. 70–79 (2008). ٢ాफ࢙ɼ޿ാ૖Ұ࿠ɼ૔ా੒‫ݾ‬ɼԘ୩྄ଠɼ‫ޒ‬ౡਖ਼༟ɼ ࡔҪमҰɿಈతλΠϜɾϘϩʔΠϯάΛՄೳʹ͢ΔΫϩο Ωϯάํࣜɼ৘ใॲཧֶձ࿦จࢽίϯϐϡʔςΟϯάγ εςϜʢACSʣɼVol. 6, No. 1, pp. 1–16 (2013). ‫ت‬ଟ‫و‬৴ɼԘ୩྄ଠɼ‫ޒ‬ౡਖ਼༟ɼࡔҪमҰɿλΠϛϯά੍ ໿Λ؇࿨͢ΔΫϩοΩϯάํࣜɼઌਐత‫جࢉܭ‬൫γϯϙ δ΢Ϝ SACSISɼpp. 347–354 (2010). Harris, D.: Skew-tolerant Circuit Design, Morgan Kaufmann Publishers, pp. 12–14 (2001). ‫ޒ‬ౡਖ਼༟ɼ૔ా੒‫ݾ‬ɼԘ୩྄ଠɼࡔҪमҰɿλΠϛϯάɾ ϑΥʔϧτ଱ੑΛ࣋ͭ Out-of-Order ϓϩηοαɼ৘ใॲ ɼVol. 6, ཧֶձ࿦จࢽίϯϐϡʔςΟϯάγεςϜʢACSʣ No. 1, pp. 17–30 (2013). Kleinberg, J. and Tardos, E.: Algorithm Design, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA (2005).. 嵧. 嵨. 憏懑憣. ਤ 22. 崴੎৲憏懑憣. ೚భಞ৕. 嵕嵫嵤嵧嵲嵺崢嵎嵤嵷嵦嵫. TF ‫ݕ‬ग़෇༩ͷྲྀΕ (5-8). c 2013 Information Processing Society of Japan . 13.

(20)