Томасуло алгоритмі - Википедия - Tomasulo algorithm

Томасуло алгоритмі Бұл компьютерлік архитектура жабдық алгоритм мүмкіндік беретін нұсқаулықтарды динамикалық жоспарлау үшін тапсырыстан тыс орындау және бірнеше орындау бірліктерін тиімді пайдалануға мүмкіндік береді. Ол әзірледі Роберт Томасуло кезінде IBM 1967 жылы және алғаш рет іске асырылды IBM System / 360 моделі 91 Ның өзгермелі нүкте бірлігі.

Томасуло алгоритмінің негізгі жаңалықтарына жатады қайта атауды тіркеу жабдықта, брондау станциялары барлық орындалу бірліктері үшін және жалпы мәліметтер шинасы (CDB), онда есептік мәндер қажет болуы мүмкін барлық брондау станцияларына таралады. Бұл әзірлемелер жақсартуға мүмкіндік береді қатар орындау пайдалану кезінде тоқтатылатын нұсқаулар таблодинг немесе басқа ертерек алгоритмдер.

Роберт Томасуло алды Эккерт - Маучли сыйлығы алгоритмдегі жұмысы үшін 1997 ж.^[1]

Іске асыру тұжырымдамалары

Томасулоның өзгермелі нүкте бірлігі

Томасуло алгоритмін жүзеге асыруға қажетті тұжырымдамалар:

Жалпы мәліметтер шинасы

Жалпы мәліметтер шинасы (CDB) брондау станцияларын функционалды блоктарға тікелей қосады. Томасулоның пікірінше, ол «параллельдікті қолдай отырып, басымдықты сақтайды».^[2]^:33 Мұның екі маңызды әсері бар:

Функционалды блоктар кез-келген операцияның нәтижесіне өзгермелі нүктелік регистрді қоспай-ақ қол жеткізе алады, бұл нәтиже бойынша күткен бірнеше қондырғыға файлдарды оқуға арналған порттарды тіркеуге қол жеткізу үшін келіспеушіліктерді шешуді күтпей-ақ жалғастыруға мүмкіндік береді.
Қауіпті анықтау және бақылауды орындау таратылады. Брондау станциялары қауіпті бір блокты емес, нұсқаулықтың орындалу уақытын бақылайды.

Нұсқаулық тәртібі

Нұсқаулар кезектілікпен шығарылады, осылайша нұсқаулықтың бірізділігі әсер ететіндей болады ерекшеліктер осы нұсқаулармен көтерілген, олар тәртіптен тыс орындалғанына қарамастан (яғни бірізді емес) тәртіптегі процессордағыдай тәртіппен жүреді.

Атауын өзгерту

Томасуло алгоритмі қолданады қайта атауды тіркеу тапсырыстан тыс орындауды дұрыс орындау. Жалпы мақсаттағы және брондау станциясының барлық регистрлері нақты мәнге немесе толтырғыш мәніне ие. Егер шығарылым кезеңінде тағайындалған тіркелімде нақты мән болмаса, толтырғыш мәні бастапқыда қолданылады. Толтырғыш мәні дегеніміз - нақты брондау станциясының нақты мәнді шығаратындығын көрсететін белгі. Бөлім аяқталғаннан кейін және нәтижені CDB-де таратқан кезде толтырғыш нақты мәнмен ауыстырылады.

Әрбір функционалды блоктың бірыңғай брондау станциясы бар. Брондау станциялары операцияны және операндты қоса, бір нұсқауды орындау үшін қажетті ақпаратты сақтайды. Функционалды блок өңдеуді бос болған кезде және нұсқаулыққа қажет барлық бастапқы операндтар нақты болған кезде бастайды.

Ерекшеліктер

Іс жүзінде, ерекшелік туралы мәртебелік ақпарат жеткіліксіз болатын ерекше жағдайлар болуы мүмкін, бұл жағдайда процессор «нақты емес» ерекшелік деп аталатын ерекше ерекшелікті көтеруі мүмкін. Нақты емес ерекшеліктер болуы мүмкін емес қалпында іске асыру, өйткені процессордың күйі тек бағдарлама ретімен өзгереді (қараңыз) RISC құбырларының ерекшеліктері ).

Ерекше жағдайды бастан кешіретін, ерекше жағдайды ескеретін нақты нұсқаулық анықталуы мүмкін бағдарламалар қайтадан басталуы немесе қайталануы мүмкін. Алайда, «нақты емес» ерекшеліктерді сезінетіндер, әдетте, қайтадан бастай немесе қайта орындай алмайды, өйткені жүйе ерекше жағдайды қабылдаған нақты нұсқауды анықтай алмайды.

Нұсқаулықтың өмірлік циклі

Төменде келтірілген үш кезең - бұл әрбір нұсқаулық берілген уақыттан бастап оның орындалуы аяқталғанға дейінгі кезеңдер.

Аңызды тіркеу

Оп - операндтарда орындалатын операцияны білдіреді
Qj, Qk - сәйкес операнд көзін шығаратын брондау станциясы (0 мәні Vj, Vk-де екенін көрсетеді)
Vj, Vk - бастапқы операндтардың мәні
A - жүктеме немесе сақтау үшін жадтың мекен-жайы туралы ақпаратты ұстау үшін қолданылады
Бос емес - бос болса 1, бос болмаса 0
Qi - (тек регистрлік блок), нәтижесі осы регистрде сақталуы керек брондау станциясы (егер бос немесе 0 болса, онда бұл регистрге ешқандай мән берілмейді)

1 кезең: шығарылым

Шығарылым кезеңінде барлық операндтар мен брондау станциялары дайын болса немесе олар тоқтап қалса, оларды орындау туралы нұсқаулар беріледі. Бұл қадамда реестрлердің аты өзгертіліп, WAR және WAW қаупі жойылады.

Нұсқаулар кезегінің бастығынан келесі нұсқауды алыңыз. Егер нұсқаулық операндтары қазір регистрлерде болса, онда
- Егер сәйкес функционалды блок болса, нұсқаулықты беріңіз.
- Басқа жағдайда, қол жетімді функционалды блок болмағандықтан, нұсқаулық станция немесе буфер бос болғанша тоқтатылады.
Әйтпесе, операндтар регистрлерде жоқ деп санауға болады, сондықтан виртуалды мәндерді қолданыңыз. Функционалды блок операндты шығаратын функционалды бірліктердің есебін жүргізу үшін нақты мәнді есептеуі керек.

Псевдокод^[3]^:180
Нұсқаулық күйі	Дейін күтіңіз	Акция немесе бухгалтерлік есеп
Іс	Станция р бос	егер (ТіркеуStat[rs].Qi¦0) { RS[р].Qj ← ТіркеуStat[rs].Qi}басқа { RS[р].Vj ← Regs[rs]; RS[р].Qj ← 0;}егер (ТіркеуStat[rt].Qi¦0) { RS[р].Qk ← ТіркеуStat[rt].Qi;}басқа { RS[р].Vk ← Regs[rt]; RS[р].Qk ← 0;}RS[р].Бос емес ← иә;ТіркеуStat[рд].Q ← р;
Жүктеу немесе сақтау	Буфер р бос	егер (ТіркеуStat[rs].Qi¦0) { RS[р].Qj ← ТіркеуStat[rs].Qi;}басқа { RS[р].Vj ← Regs[rs]; RS[р].Qj ← 0;}RS[р].A ← имм;RS[р].Бос емес ← иә;
Тек жүктеу		ТіркеуStat[rt].Qi ← р;
Тек дүкенде		егер (ТіркеуStat[rt].Qi¦0) { RS[р].Qk ← ТіркеуStat[rt].Qi;}басқа { RS[р].Vk ← Regs[rt]; RS[р].Qk ← 0};

Томасуло алгоритмінің мысалы^[4]

2 кезең: орындау

Орындау кезеңінде нұсқаулық операциялары жүзеге асырылады. Нұсқаулар RAW қаупін жойып, барлық операндтар пайда болғанға дейін осы қадамға кешіктіріледі. Бағдарламаның дұрыстығы жад арқылы қауіпті жағдайлардың алдын алу үшін мекен-жайды тиімді есептеу арқылы сақталады.

Егер операндтардың біреуі немесе бірнешеуі әлі қол жетімді болмаса, онда: операндтың CDB-де пайда болғанын күтіңіз.
Барлық операндтар қол жетімді болған кезде, егер: егер нұсқаулық жүктеме немесе дүкен болса
- Негізгі тіркеуге қол жетімді болған кезде тиімді мекен-жайды есептеңіз және оны жүктеу / сақтау буферіне салыңыз
  - Егер нұсқаулық жүктеме болса, оны: жад бірлігі қол жетімді болғаннан кейін орындаңыз
  - Басқа жағдайда, егер нұсқаулық дүкен болса: мәнді жад бөліміне жібермес бұрын оның сақталуын күтіңіз
Басқа нұсқаулар арифметикалық логикалық бірлік (ALU) жұмысы, содан кейін: нұсқауды сәйкес функционалды блокта орындайды

Псевдокод^[3] ^:180
Нұсқаулық күйі	Дейін күтіңіз	Акция немесе бухгалтерлік есеп
ФП жұмысы	(RS [r] .Qj = 0) және (RS [r] .Qk = 0)	Есептеу нәтижесі: операндтар Vj және Vk
1-қадамды жүктеңіз / сақтаңыз	`RS [r] .Qj = 0` & r - жүкті сақтау кезегінің бастығы	RS [r] .A ← RS [r] .Vj + RS [r] .A;
2-қадамды жүктеңіз	1-қадамды жүктеңіз	Оқу `Mem [RS [r] .A]`

3 кезең: нәтиже жазу

Нәтиже жазу кезеңінде ALU операцияларының нәтижелері регистрлерге, ал сақтау операциялары жадқа қайта жазылады.

Егер нұсқаулық ALU операциясы болса
- Егер нәтиже қол жетімді болса, онда оны CDB-ге жазыңыз және сол жерден регистрлерге және осы нәтижені күтетін кез-келген брондау станциясына жазыңыз.
Басқа, егер нұсқаулық дүкен болған болса: осы қадамда деректерді жадқа жазыңыз

Псевдокод^[3] ^:180

Нұсқаулық күйі

Дейін күтіңіз

Акция немесе бухгалтерлік есеп

FP жұмысы немесе жүктеме

Орындау уақыты аяқталды р & CDB бар

	∀х(егер (ТіркеуStat[х].Qi = р) {		рег[х] ← нәтиже;		ТіркеуStat[х].Qi = 0	});	∀х(егер (RS[х].Qj = р) {		RS[х].Vj ← нәтиже;		RS[х].Qj ← 0; 	});	∀х(егер (RS[х].Qk = р) {		RS[х].Vk ← нәтиже;		RS[х].Qk ← 0;	});	RS[р].Бос емес ← жоқ;

Дүкен

Орындау уақыты аяқталды r & RS [r] .Qk = 0

	Мем[RS[р].A] ← RS[р].Vk;	RS[р].Бос емес ← жоқ;

Алгоритмді жетілдіру

Томасуло алгоритміндегі брондау станциялары, регистрдің атауын өзгерту және жалпы мәліметтер шинасы ұғымдары жоғары өнімді компьютерлерді жобалауда айтарлықтай жетістіктер ұсынады.

Брондау станциялары деректерге тәуелділік және басқа сәйкессіздіктер болған кезде операндтарды күтуге жауапкершілікті алады, мысалы, сақтаудың қол жетімділік уақыты мен схеманың жылдамдығы өзгереді, осылайша функционалды блоктар босатылады. Бұл жақсарту өзгермелі нүктенің ұзақ кідірісі мен жадқа қол жеткізуді жеңеді. Атап айтқанда, алгоритм кэштің жіберілуіне төзімді. Сонымен қатар, бағдарламашылар оңтайландырылған кодты енгізуден босатылады. Бұл тәуелділіктерді сақтау және параллельділікті ынталандыру үшін жалпы мәліметтер шинасы мен брондау станциясының бірлескен жұмысының нәтижесі.^[2]^:33

Брондау бекеттеріндегі нұсқаулар үшін операндтарды қадағалап, атауды аппаратурада тіркеу алгоритмді азайтады жазғаннан кейін оқу (RAW) және жояды жазудан кейін жазу (WAW) және Оқығаннан кейін жазу (СОҒЫС) компьютерлік архитектура қауіптер. Бұл сауда орындары үшін қажет болатын бос уақытты азайту арқылы өнімділікті жақсартады.^[2]^:33

Алгоритмнің маңызды жетілдірілуі - бұл белгілі бір құбыр құрылымымен ғана шектелмейді. Бұл жетілдіру алгоритмді бірнеше шығарылымдық процессорлармен кеңірек қабылдауға мүмкіндік береді. Сонымен қатар, алгоритм филиал спекуляциясын қосу үшін кеңейтіледі.^[3] ^:182

Өтініштер мен мұра

Томасуло алгоритмі, IBM-ден тыс, System / 360 Model 91 архитектурасында енгізілгеннен кейін бірнеше жыл бойы қолданылмаған. Алайда, бұл 1990 жылдардың ішінде 3 себеп бойынша пайдаланудың едәуір өсуін байқады:

Кэштер үйреншікті жағдайға айналғаннан кейін, Tomasulo алгоритмінің кэшті жіберіп алудан туындаған жүктеме уақытында параллельділікті сақтау қабілеті процессорларда құнды болды.
Алгоритмнің динамикалық жоспарлауы және салалық спекуляциясы өнімділікке көмектесті, өйткені процессорлар көбірек нұсқаулар берді.
Нарықтық бағдарламалық жасақтаманың таралуы бағдарламашылардың белгілі бір құбыр құрылымы үшін жинақтауды қаламайтындығын білдірді. Алгоритм кез-келген құбыр сәулетімен жұмыс істей алады, сондықтан бағдарламалық жасақтама архитектураға аз модификацияларды қажет етеді.^[3] ^:183

Көптеген заманауи процессорлар Томасулоның түпнұсқалық алгоритмінің туындысы, соның ішінде танымал болып табылатын жоспарлаудың динамикалық схемаларын жүзеге асырады Intel x86-64 чиптер.^[5]^{[тексеру сәтсіз аяқталды ]}^[6]

Сондай-ақ қараңыз

Әдебиеттер тізімі

^ «Роберт Томасуло - сыйлық иегері». ACM Awards. ACM. Алынған 8 желтоқсан 2014.
^ ^а ^б ^c Томасуло, Роберт Марко (Қаңтар 1967). «Бірнеше арифметикалық бірлікті пайдаланудың тиімді алгоритмі». IBM Journal of Research and Development. IBM. 11 (1): 25–33. дои:10.1147 / рд.111.0025. ISSN 0018-8646.
^ ^а ^б ^c ^г. ^e Хеннесси, Джон Л .; Паттерсон, Дэвид А. (2012). Компьютерлік архитектура: сандық тәсіл. Уолтам, MA: Elsevier. ISBN 978-0123838728.
^ «CSE P548 - Томасуло» (PDF). washington.edu. Вашингтон университеті. 2006 ж. Алынған 8 желтоқсан 2014.
^ Intel 64 және IA-32 Architectures бағдарламалық жасақтамасын әзірлеушіге арналған нұсқаулық (Есеп). Intel. Қыркүйек 2014. Алынған 8 желтоқсан 2014.
^ Йога, Адарш. «Intel Core микроархитектурасындағы Томасуло алгоритмі мен динамикалық жоспарлау арасындағы айырмашылықтар». Бузер. Алынған 4 сәуір 2016.

Әрі қарай оқу

Савард, Джон Дж. Г. (2018) [2014]. «Түтікшелі және тапсырыссыз орындау». квадиблок. Мұрағатталды түпнұсқасынан 2018-07-03. Алынған 2018-07-16.

Сыртқы сілтемелер

[1] «Роберт Томасуло - сыйлық иегері». ACM Awards. ACM. Алынған 8 желтоқсан 2014.

[tomasulo-2] а ^б ^c Томасуло, Роберт Марко (Қаңтар 1967). «Бірнеше арифметикалық бірлікті пайдаланудың тиімді алгоритмі». IBM Journal of Research and Development. IBM. 11 (1): 25–33. дои:10.1147 / рд.111.0025. ISSN 0018-8646.

[hennessy-3] а ^б ^c ^г. ^e Хеннесси, Джон Л .; Паттерсон, Дэвид А. (2012). Компьютерлік архитектура: сандық тәсіл. Уолтам, MA: Elsevier. ISBN 978-0123838728.

[4] «CSE P548 - Томасуло» (PDF). washington.edu. Вашингтон университеті. 2006 ж. Алынған 8 желтоқсан 2014.

[intel-5] Intel 64 және IA-32 Architectures бағдарламалық жасақтамасын әзірлеушіге арналған нұсқаулық (Есеп). Intel. Қыркүйек 2014. Алынған 8 желтоқсан 2014.

[adusan-6] Йога, Адарш. «Intel Core микроархитектурасындағы Томасуло алгоритмі мен динамикалық жоспарлау арасындағы айырмашылықтар». Бузер. Алынған 4 сәуір 2016.

[1]

[2]

[3]

[4]

[5]

[6]