User:Vardui Xudatyan/ավազարկղ

Tomasulo ալգրիթմը սարքակազմ ալգորիթմ է , որը մշակվել է IBM-ից 1967թ.-ին Ռոբերտ Տոմասուլոյի կողմից: Այն թույլ է տալիս կատարել հաջորդական հրահանգներ, որոնք սովորաբար կանգնեցվել են որոշակի կախվածությամբ պայմանավորված: Այն առաջին անգամ իրագործվել է IBM System/360 Model 91-ի համար փոփոխական կետով միավորից: Այս ալգորիթմը տարբերվում է աղյուսակայինից նրանով, որ սա օգտագործվում է ռեգիստրը անվանափոխելիս: Որտեղ աղյուսակայինը որոշում է WAW(Write-after-Write)-ի և WAR(Write-after-Read)-ի հետ կապված խնդիրները, վտանգները վերացնելով, ռեգիստրի մնալը թույլ է տալիս շարունակական հրահանգների թողարկումը:Tomasulo ալգորիթմն օգտագործում է նաև ընդհանուր տվյալների բազա(CDB), որի համարժեքները տարածվում են բոլոր անհրաժեշտ ամրագրման կայաններում:Սա թույլ է տալիս բարելավել զուգահեռ կատարման հրահանգները, որը կարող է մոլորեցնել աղյուսակայինի օգտագործման տակ:

Ռոբերտ Տոմասուլոն 1997թ.-ին ստացել է Eckert-Mauchly մրցանակ այս ալգորիթմի համար:

Կատարման հասկացություններ

Tomasulo ալգորիթմի իրականացման համար անհրաժեշտ հասկացությունները հետևյալն են.

• Հրահանգները տրվում են հերթականությամբ, որպեսզի հաջորդական հրահանգների հետևանքները, ինչպիսիք են բացառությունների կողմից բարձրացված ցուցումները, տեղի են ունենում նույն կարգով, ինչպես նրանք տեղի կունենային ոչ խողովակաշարված պրոցեսում, անկախ նրանից, որ իրենք գործարկված են ոչ հերթականությամբ:

• Բոլոր ընդհանուր նշանակության և ամրագրման կայանների գրանցուները զբաղեցնում են կամ իրական, կամ վիրտուալ արժեքներ:Եթե իրական արժեքը անհասանելի է նշանակման վայրի գրանցամատյանում թողարման փուլի ընթացքում, ապա վիրտուալ արժեքը նախապես օգտագործվել է:Ֆունկցիոնալ մասը, որը հաշվում է իրական մասը նշանակվում է որպես վիրտուալ արժեք: Վիրտուալ գրանցման արժեքները ձևափոխվում են իրական արժեքների, հենց որ նշանակված ֆունկցիոնալ մասն ավարտում է իր հաշվարկը:

• Ֆունկցիոնալ մասերը օգտագործում են ամրագրման կայանները բազմաթիվ ակոսների հետ:Ամեն ակոս ունի անհրաժեշտ ինֆորմացիա կատարելու մի հանձնարարություն , հերառյալ շահագործումը և օպերանդները: Ֆունկցիոնալ մասն սկսում է գործընթացը, երբ այն ազատ է և երբ բոլոր անհրաժեշտ տրամաբանական աղբյուրների ցուցումներն իրական են:

Հրահանգման պարբերաշրջան

Ստորև թվարկված են այն երեք փուլերը, որոնց միջոցով ամեն մի հրահանգ անցնում է թողարկնած ժամանակից մի ժամանակի, որի կատարողականն ամբողջական է:

ՓՈՒԼ 1-ին: Գրառում.

Գրառման փուլում հրահանգները տրվում են կատարման , եթե բոլոր օպերանդները և ամրագրման կայանները պատրաստ են կամ կանգնեցված են: Գրառումները վերանվանվել են այս քայլով, վերացնելով WAR և WAW վտանգները:

• Առբեռնման հաջորդ ցուցումը հրահանգների հերթի ղեկավարից է:Եթե հրահանգի օպերանդները ներկա պահին ռեգիստրում են, ապա…
  • Եթե համապատասխան ֆունկցիոնալ մասը հասանելի է, գրառել հրահանգը:
  • Հակառակ դեպքում, քանի որ չկա հասանելի ֆունկցիոնալ մաս , կանգնեցնել հրամանը մինչև կայանը կամ պահենին ազատվեն:
• Այլապես մենք կարող ենք գրառել օպերանդները , որոնք ռեգիստրում չեն, այսպիսով օգտագործելով վիրտուալ արժեքներ. ֆունկցիոնալ մասը պետք է հաշվարկվի իրական արժեքով, որպեսզի պահենք այն ֆունցիոնալ մասերը , որոնք կարտադրեն օպերանդներ:

ՓՈՒԼ 2-րդ: Կատարում.

Իրականացման փուլում հրահանգված գործողություններն իրագործվում են: Հրահանգները ուշանում են այդ քայլին, մինչև բոլոր իրենց օպերանդները հասանելի են , վերացնելով RAW վտանգը:Ծրագրի կոռեկտությունը պահպանվում է գործող հասցեն հաշվարկելու միջոցով, հիշողության միջոցավ կանխելով վտանգը:

• Եթե մեկ կամ մի քանի օպերանդներ դեռ հասանելի չէ, ապա սպասե,լորպեսզի օպերանդը դառնա հասանելի CDB-ով:
• Եթե բոլոր օպերանդները հասանելի են, ապա հրահանգը բեռնվում է կամ պահվում:
  • Հաշվարկել գործող հասցեն, երբ ռեգիստրի բազան հասանելի է և տեղադրել այն բեռնում/պահում պահենիում:
    • Եթե հրահանգը բեռնված է, ապա կատարել հենց որ հիշողության մասը դառնա հասանելի:
    • Այլապես, եթե հրահանգը պահված է, ապա սպասել արժեքի պահվելուն նախքան հիշողության բաժին ուղարկելը:
• Հակառակ դեպքում, եթե հրահանգը ALU գործողություն է, ապա կատարել հրահանգը համապատասխան ֆունկցիոնալ մասում:

ՓՈՒԼ 3-րդ: Արդյունքի գրանցում.

Արդյունքի գրանցման փուլում ALU գործողություննների արդյունքները գրված են ետգրանցման մեջ, պահման գործողությունները գրված են ետհիշողության մեջ:

• Եթե հրահանգը եղել է ALU գործողություն.
  • Եթե արդյունքը հասանելի է , ապա գրել դա CDB –ում, այնտեղից ռեգիստրների մեջ, և ցանկացած ամրագրման կայան սպասում է այս արդյունքին:
• Այլապես, եթե հրահանգը պահպանվել է, ապա գրել տվյալները հիշողության մեջ այս քայլի ընթացքում:

Տեսնել նաև

• Re-order buffer
• Instruction level parallelism
• Out-of-order execution

Արտաքին կապեր

• Dynamic Scheduling - Tomasulo's Algorithm

Մատենագիտություն

• An Efficient Algorithm for Exploiting Multiple Arithmetic Units, IBM Journal of Research and Development, 11(1):25-33, January 1967.
• WebHASE: Tomasulo's Algorithm: HASE Java applet simulation of the Tomasulo's Algorithm, Institute for Computing Systems Architecture, Edinburgh University.
• TOMASULO'S ALGORITHM FOR DYNAMIC SCHEDULING
• Computer Architecture: A Quantitative Approach, John L. Hennessy & David A. Patterson

Category:Algorithms Category:Instruction processing