Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Цифрлық схема
Digital circuit
Компьютерлік архитектурада тармақты болжаушы – бұл тармақтың (мысалы, if–then–else конструкциясы) қай бағытқа бұрылатынын нақты белгілі болмас бұрын болжауға тырысатын цифрлық схема. Тармақты болжаушының мақсаты – нұсқаулар конвейеріндегі ағынды жақсарту. Тармақты болжаушылар көптеген қазіргі заманғы конвейерлі микропроцессор архитектураларында жоғары өнімділікке қол жеткізуде маңызды рөл атқарады. Екі тармақты тармақтану әдетте шартты секіру нұсқауларымен іске асырылады. Шартты секіру "орындалуы" мүмкін, яғни бағдарлама жадындағы басқа орынға секіру, немесе "орындалмауы" мүмкін, және шартты секіруден кейін дереу орындауды жалғастыру. Шартты секірудің орындалатыны немесе орындалмайтыны шарт есептелгенге және нұсқау конвейерінде орындау кезеңінен өткенге дейін белгілі емес (1-суретті қараңыз). Тармақты болжау болмаса, процессор келесі нұсқау конвейердегі алу кезеңіне кірмес бұрын шартты секіру нұсқаулары орындау кезеңінен өтуін күтуге мәжбүр болады. Тармақты болжаушы шартты секірудің орындалу ықтималдығын болжауға тырысады. Содан кейін ең ықтимал деп болжанған тармақ алынып, болжамды түрде орындалады. Егер кейіннен болжаудың қате екендігі анықталса, онда болжамды түрде орындалған немесе ішінара орындалған нұсқаулар жойылады және конвейер дұрыс тармақпен қайта басталады, бұл кідіріске әкеледі. Тармақты дұрыс болжамаған жағдайда жоғалған уақыт конвейердегі алу кезеңінен орындау кезеңіне дейінгі кезеңдер санына тең болады. Қазіргі микропроцессорлардың конвейерлері көбінесе өте ұзын болады, сондықтан дұрыс болжамағандағы кідіріс 10 мен 20 сағат циклы арасында болуы мүмкін. Нәтижесінде, конвейерді ұзарту күрделірек тармақты болжаушыға деген қажеттілікті арттырады. Шартты секіру нұсқаулары алғаш рет кездескенде, болжауды негіздеу үшін көп ақпарат болмайды. Бірақ тармақты болжаушы тармақтардың орындалғанын немесе орындалмағанын тіркеп алады. Егер ол бұрын бірнеше рет кездескен шартты секірумен кездессе, онда ол болжамды тарихқа негіздеуге болады. Мысалы, тармақты болжаушы шартты секірудің көбінесе орындалатынын немесе әр екінші рет орындалатынын анықтауы мүмкін. Тармақты болжау, тармақ мақсатын болжаудан өзгеше. Тармақты болжау шартты секірудің орындалатынын немесе орындалмайтынын болжауға тырысады. Тармақ мақсатын болжау, шартты немесе шартсыз секірудің мақсатын оны кодтау және нұсқауды орындау арқылы есептеу алдында болжауға тырысады. Тармақты болжау және тармақ мақсатын болжау көбінесе бір схемаға біріктіріледі.
In computer architecture, a branch predictor is a digital circuit that tries to guess which way a branch (e. g., an if–then–else structure) will go before this is known definitively. The purpose of the branch predictor is to improve the flow in the instruction pipeline. Branch predictors play a critical role in achieving high performance in many modern pipelined microprocessor architectures. Two way branching is usually implemented with a conditional jump instruction. A conditional jump can either be "taken" and jump to a different place in program memory, or it can be "not taken" and continue execution immediately after the conditional jump. It is not known for certain whether a conditional jump will be taken or not taken until the condition has been calculated and the conditional jump has passed the execution stage in the instruction pipeline (see fig. 1). Without branch prediction, the processor would have to wait until the conditional jump instruction has passed the execute stage before the next instruction can enter the fetch stage in the pipeline. The branch predictor attempts to avoid this waste of time by trying to guess whether the conditional jump is most likely to be taken or not taken. The branch that is guessed to be the most likely is then fetched and speculatively executed. If it is later detected that the guess was wrong, then the speculatively executed or partially executed instructions are discarded and the pipeline starts over with the correct branch, incurring a delay. The time that is wasted in case of a branch misprediction is equal to the number of stages in the pipeline from the fetch stage to the execute stage. Modern microprocessors tend to have quite long pipelines so that the misprediction delay is between 10 and 20 clock cycles. As a result, making a pipeline longer increases the need for a more advanced branch predictor. The first time a conditional jump instruction is encountered, there is not much information to base a prediction on. But the branch predictor keeps records of whether branches are taken or not taken. When it encounters a conditional jump that has been seen several times before, then it can base the prediction on the history. The branch predictor may, for example, recognize that the conditional jump is taken more often than not, or that it is taken every second time. Branch prediction is not the same as branch target prediction. Branch prediction attempts to guess whether a conditional jump will be taken or not. Branch target prediction attempts to guess the target of a taken conditional or unconditional jump before it is computed by decoding and executing the instruction itself. Branch prediction and branch target prediction are often combined into the same circuitry.
Статикалық тармақты болжау
Статикалық болжам – ең қарапайым тармақ болжамдау техникасы, себебі ол кодтың динамикалық орындалу тарихы туралы ақпаратқа сүйенбейді. Оның орнына, ол тармақтың нәтижесін тек қана тармақ нұсқауына сүйене отырып болжайды. SPARC және MIPS (алғашқы екі коммерциялық RISC архитектурасы) жүзеге асырылғанда бір бағытты статикалық тармақ болжамдауды қолданды: олар шартты секіру әрқашан орындалмайды деп болжайтын, сондықтан әрқашан келесі тізбекті нұсқауды алатын. Тек тармақ немесе секіру бағаланып, орындалған болып табылған жағдайда ғана нұсқау көрсеткіші тізбексіз мекенжайға орнатылады. Екі процессор да тармақтарды декодтау кезеңінде бағалайды және бір циклді нұсқауды алады. Нәтижесінде, тармақ мақсатының қайталануы екі циклды құрайды, ал машина әрқашан орындалған тармақтан кейін дереу нұсқауды алады. Екі архитектура да осы алынған нұсқауларды пайдалану үшін тармақ кешіктіру орындарын анықтайды. Статикалық болжамның жетілдірілген түрі артқа қарайғы тармақтар орындалатынын, ал алға қарайғы тармақтар орындалмайтынын болжайды. Артқа қарайғы тармақ – бұл мақсатты мекенжайы өзінің мекенжайынан төмен болатын тармақ. Бұл техника циклдардың болжамдау дәлдігіне көмектеседі, себебі циклдар көбінесе артқа қарай бағытталған тармақтар болып табылады және көбінесе орындалады. Кейбір процессорлар кодқа тармақ болжамдау ұсыныстарын енгізуге мүмкіндік береді, осылайша статикалық болжам орындалу керек пе, жоқ па, дегенді анықтауға болады. Intel Pentium 4 тармақ болжамдау ұсыныстарын қабылдайды, бірақ бұл мүмкіндік кейінгі Intel процессорларында қолданылмай қалды. Статикалық болжам кейбір процессорларда динамикалық тармақ болжамдаумен бірге, динамикалық болжамдаушылар жеткілікті ақпаратқа ие болмаған жағдайда, резервтік техника ретінде қолданылады. Motorola MPC7450 (G4e) және Intel Pentium 4 осы әдісті резервтік ретінде пайдаланады. Статикалық болжамда барлық шешімдер бағдарлама орындалуына дейін, компиляция кезінде қабылданады.
Static prediction is the simplest branch prediction technique because it does not rely on information about the dynamic history of code executing. Instead, it predicts the outcome of a branch based solely on the branch instruction. The early implementations of SPARC and MIPS (two of the first commercial RISC architectures) used single direction static branch prediction: they always predict that a conditional jump will not be taken, so they always fetch the next sequential instruction. Only when the branch or jump is evaluated and found to be taken, does the instruction pointer get set to a non sequential address. Both CPUs evaluate branches in the decode stage and have a single cycle instruction fetch. As a result, the branch target recurrence is two cycles long, and the machine always fetches the instruction immediately after any taken branch. Both architectures define branch delay slots in order to utilize these fetched instructions. A more advanced form of static prediction presumes that backward branches will be taken and that forward branches will not. A backward branch is one that has a target address that is lower than its own address. This technique can help with prediction accuracy of loops, which are usually backward pointing branches, and are taken more often than not taken. Some processors allow branch prediction hints to be inserted into the code to tell whether the static prediction should be taken or not taken. The Intel Pentium 4 accepts branch prediction hints, but this feature was abandoned in later Intel processors. Static prediction is used as a fall back technique in some processors with dynamic branch prediction when dynamic predictors do not have sufficient information to use. Both the Motorola MPC7450 (G4e) and the Intel Pentium 4 use this technique as a fall back. In static prediction, all decisions are made at compile time, before the execution of the program.
Екі деңгейлі болжаушы
Екі деңгейлі тармақ болжаушысы, сонымен қатар корреляцияға негізделген тармақ болжаушысы деп те аталады, екі өлшемді есептегіштер кестесін пайдаланады, бұл кесте "үлгі тарихы кестесі" деп те белгілі. Кестедегі жазбалар екі биттік есептегіштер болып табылады.
The Two Level Branch Predictor, also referred to as Correlation Based Branch Predictor, uses a two dimensional table of counters, also called "Pattern History Table". The table entries are two bit counters.
Екі деңгейлі бейімделетін болжаушы
Егер if-кестені үш рет орындаса, үшінші орындауда қабылданған шешім алдыңғы екеуінің орындалғанына немесе орындалмағанына байланысты болуы мүмкін. Мұндай жағдайларда екі деңгейлі бейімделу болжаушы қанығу санағыштан тиімдірек жұмыс істейді. Әр екінші рет орындалатын немесе басқа да үлгілі түрде қайталанатын шартты секірулер қанығу санағышымен жақсы болжалмайды. Екі деңгейлі бейімделу болжаушы тармақтың соңғы n оқиғасының тарихын есте сақтайды және әр 2n мүмкін тарих үлгісі үшін бір қанығу санағышын қолданады. Бұл әдіс 3-суретте көрсетілген. n = 2 мысалын қарастырайық. Бұл тармақтың соңғы екі оқиғасы екі биттік ауысу тізілімінде сақталады дегенді білдіреді. Бұл тармақ тарихы тізілімінде төрт түрлі екілік мән болуы мүмкін: 00, 01, 10 және 11, мұнда нөл – "орындалмаған", ал бір – "орындалған" дегенді білдіреді. Үлгі тарихы кестесінде әрбір тармақ үшін төрт жазба бар, олардың әрқайсысы 22 = 4 мүмкін тармақ тарихына сәйкес келеді, ал кестедегі әрбір жазбада әр тармақ үшін 2-суреттегідей екі биттік қанығу санағышы бар. Тармақ тарихы тізілімі төрт қанығу санағышының қайсысын пайдалану керектігін таңдау үшін қолданылады. Егер тарих 00 болса, онда бірінші санағыш қолданылады; егер тарих 11 болса, онда төрт санағыштың соңғысы қолданылады. Мысалы, шартты секіру әр үшінші рет орындалады делік. Бұл жағдайда, үлгі тарихы кестесіндегі 00 нөмірі "қатты орындалған" күйіне өтеді, яғни екі нөлден кейін бір келеді. 01 нөмірі "қатты орындалмаған" күйіне өтеді, яғни 01-ден кейін нөл келеді. 10 нөмірі үшін де осыған ұқсас жағдай орын алады, ал 11 нөмірі ешқашан қолданылмайды, себебі екі бірдің қатары болмайды. n биттік тарихы бар екі деңгейлі бейімделу болжаушының жалпы ережесі – барлық n биттік кіші тізбектер әртүрлі болса, кез келген кезеңдегі кез келген қайталанатын тізбекті болжауға болады. 1991 жылғы алғашқы жарияланудан бері бұл әдіс кең таралды. Бұл болжау әдісінің түрлері қазіргі заманғы микропроцессорлардың көпшілігінде қолданылады.
If an if statement is executed three times, the decision made on the third execution might depend upon whether the previous two were taken or not. In such scenarios, a two level adaptive predictor works more efficiently than a saturation counter. Conditional jumps that are taken every second time or have some other regularly recurring pattern are not predicted well by the saturating counter. A two level adaptive predictor remembers the history of the last n occurrences of the branch and uses one saturating counter for each of the possible 2n history patterns. This method is illustrated in figure 3. Consider the example of n = 2. This means that the last two occurrences of the branch are stored in a two bit shift register. This branch history register can have four different binary values, 00, 01, 10, and 11, where zero means "not taken" and one means "taken". A pattern history table contains four entries per branch, one for each of the 22 = 4 possible branch histories, and each entry in the table contains a two bit saturating counter of the same type as in figure 2 for each branch. The branch history register is used for choosing which of the four saturating counters to use. If the history is 00, then the first counter is used; if the history is 11, then the last of the four counters is used. Assume, for example, that a conditional jump is taken every third time. The branch sequence is 001001001 In this case, entry number 00 in the pattern history table will go to state "strongly taken", indicating that after two zeroes comes a one. Entry number 01 will go to state "strongly not taken", indicating that after 01 comes a zero. The same is the case with entry number 10, while entry number 11 is never used because there are never two consecutive ones. The general rule for a two level adaptive predictor with an n bit history is that it can predict any repetitive sequence with any period if all n bit sub sequences are different. Since the initial publication in 1991, this method has become very popular. Variants of this prediction method are used in most modern microprocessors.
Екі деңгейлі нейрондық болжаушы
Екі деңгейлі тармақ болжаушысы ұсынылды, онда екінші деңгей нейрондық желімен алмастырылған.
A two level branch predictor where the second level is replaced with a neural network has been proposed.
Жергілікті филиалдың болжамы
Жергілікті тармақ болжаушының әр шартты секіру нұсқаулығы үшін жеке тарих буфері болады. Ол екі деңгейлі бейімделетін болжаушыны пайдалана алады. Тарих буфері әрбір шартты секіру нұсқаулығы үшін бөлек, ал үлгі тарихы кестесі де бөлек болуы мүмкін, немесе ол барлық шартты секірулер арасында ортақ болуы мүмкін. Intel Pentium MMX, Pentium II және Pentium III процессорларында жергілікті 4 биттік тарихы және әрбір шартты секіру үшін 16 жазбадан тұратын жергілікті үлгі тарихы кестесі бар жергілікті тармақ болжаушылары қолданылады. SPEC'89 сынақтарында өте үлкен жергілікті болжаушылардың дұрыстығы 97,1%-ға жетеді. Жергілікті және жаһандық болжау принциптерін жергілікті және жаһандық тармақ тарихын біріктіру арқылы үйлестіреді, сондай-ақ бағдарлама санауышынан (program counter) кейбір биттерді қосуға болады. Тәжірибелер VIA Nano процессоры осы техниканы қолдануы мүмкін екенін көрсетеді.
A local branch predictor has a separate history buffer for each conditional jump instruction. It may use a two level adaptive predictor. The history buffer is separate for each conditional jump instruction, while the pattern history table may be separate as well or it may be shared between all conditional jumps. The Intel Pentium MMX, Pentium II, and Pentium III have local branch predictors with a local 4 bit history and a local pattern history table with 16 entries for each conditional jump. On the SPEC'89 benchmarks, very large local predictors saturate at 97.1% correct. combines the local and global prediction principles by concatenating local and global branch histories, possibly with some bits from the program counter as well. Tests indicate that the VIA Nano processor may be using this technique.
Гибридті болжаушы
Гибридтік болжаушы, сондай-ақ біріктірілген болжаушы деп аталады, бірнеше болжау механизмін іске асырады. Соңғы болжау бұрынғыда ең жақсы болжау жасаған болжаушыларды есте сақтайтын мета-болжаушыға немесе әртүрлі болжаушылардың тақ санына негізделген көпшілік дауыс беру функциясына сүйенеді. Скотт Макфарлинг 1993 жылғы мақаласында біріктірілген тармақ болжауын ұсынды. Intel және AMD компанияларының жаңа процессорлары екі деңгейлі бейімделмелі болжаушыны қолдану арқылы тура емес тармақтарды болжауға мүмкіндік береді. Мұндай нұсқау тарих буферіне бір биттен артық үлес қосады. IBM-нің zEC12 және одан кейінгі z/Architecture процессорлары, берілген нұсқау үшін тармақ болжаушы жазуын, жалпы мақсаттағы тіркеуіштің мазмұнына бірден ығысу мәнін қосу арқылы құрастырылған тармақ мақсатының мекенжайымен алдын ала жүктеуге мүмкіндік беретін нұсқауды қолдайды. Бұл механизмсіз процессорлар тура емес секіруді соңғы реттегідей мақсатқа бару үшін болжайды.
A hybrid predictor, also called combined predictor, implements more than one prediction mechanism. The final prediction is based either on a meta predictor that remembers which of the predictors has made the best predictions in the past, or a majority vote function based on an odd number of different predictors. Scott McFarling proposed combined branch prediction in his 1993 paper. Newer processors from Intel and AMD can predict indirect branches by using a two level adaptive predictor. This kind of instruction contributes more than one bit to the history buffer. The zEC12 and later z/Architecture processors from IBM support a instruction that can preload the branch predictor entry for a given instruction with a branch target address constructed by adding the contents of a general purpose register to an immediate displacement value. Processors without this mechanism will simply predict an indirect jump to go to the same target as it did last time.