Кіріспе
Компьютерлік бағдарламалаудағы шартты операторлардың түрлері
Компьютерлік архитектурада, шартты кодтау – шартты тармақ машиналық нұсқауларымен іске асырылатын басқарудың шартты берілуіне балама болатын мүмкіндік. Шартты кодтау, predicate (шарт) арқылы басқарылатын, шартты (кодталған) тармақсыз нұсқаулармен жұмыс істейді. Бұл predicate – нұсқаудың архитектуралық жай-күйін өзгертуге рұқсат беруі үшін қолданылатын бульдік мән. Егер нұсқаулықта көрсетілген шарт дұрыс болса, нұсқаулық архитектуралық жай-күйін өзгертеді; әйтпесе, архитектуралық жай-күй өзгеріссіз қалады. Мысалы, кодталған көшіру нұсқаулығы (шартты көшіру) тек шарт дұрыс болса ғана мақсатты өзгертеді. Осылайша, шартты тармақты пайдаланудың орнына, тармақтың орындалуын бақылайтын шартқа сәйкес нұсқауды немесе нұсқаулар тізбегін таңдаудың орнына, орындалатын нұсқаулар сол шартпен байланысты болады, осылайша олар шарт дұрыс немесе бұрыс екеніне байланысты орындалады немесе орындалмайды. Векторлық процессорлар, кейбір SIMD ISA (мысалы, AVX2 және AVX 512) және жалпы алғанда GPU-лар шартты кодтауды кеңінен пайдаланады, өңделіп жатқан векторлық тізілімдердегі сәйкес элементтерге шартты маска векторының бір битін қолданады, ал скалярлық нұсқаулар жиынтығындағы скалярлық кодтауға тек бір шарт биті қажет. Шартты маскалар векторлық өңдеуде ерекше тиімді болады, егер әрбір векторлық элемент үшін жағдай кодтарының массиві кейіннен келесі векторлық нұсқауларға қолданылатын шартты маскаларға қайта жіберілсе.
Шолу
Көптеген компьютерлік бағдарламаларда шартты код болады, ол алдын ала анықтау мүмкін емес факторларға байланысты, мысалы, пайдаланушының енгізген мәліметтеріне байланысты белгілі бір жағдайларда ғана орындалады. Көптеген процессорлар тізбек бойынша келесі нұсқауды ғана орындағандықтан, дәстүрлі шешім – бағдарламаның басқа код бөліміне шартты түрде өтуіне мүмкіндік беретін тармақтау нұсқауларын қосу, осылайша тізбек бойынша келесі қадамды өзгерту. Бұл, процессорлардың нұсқаулық құбырларын (instruction pipelining) енгізу арқылы өнімділікті арттыра бастағанға дейін жеткілікті болды, бірақ тармақтаулар осы құбырдың жұмысын баяулатады. Туындаған мәселелердің толық сипаттамасы мен танымал шешімі үшін, тармақ болжаушы (branch predictor) деген мақаланы қараңыз. Әйгілі болғандай, әдетте тармақтануға тәуелді кодтың жиі кездесетін үлгілерінің біріне әлдеқайда әдемі шешім бар. Келесі псевдокодты қарастырайық:
Артықшылықтар
Бағдарламалық кодтың өте кішкентай бөліктеріне секіруден аулақ болу, құбыржолды орындаудың тиімділігін арттыру және кэшпен байланысты проблемаларды болдырмау – болжамның басты мақсаты. Оның тағы да бірнеше айқын артықшылықтары бар: дәстүрлі түрде қарапайым арифметикалық және биттік амалдармен есептелетін функциялар, болжамды нұсқауларды қолдану арқылы жылдам орындалуы мүмкін. Әртүрлі болжамдармен жабдықталған нұсқауларды бір-бірімен және шартсыз кодпен үйлестіруге болады, бұл нұсқауларды тиімді жоспарлауға және осылайша өнімділікті жақсартуға мүмкіндік береді. Қажетсіз тармақталу нұсқауларын жою, тармақтарды болжау механизмдерінің жүктемесін азайту арқылы қажетті тармақтардың, мысалы, циклдардың жылдам орындалуын қамтамасыз етеді. Сонымен қатар, терең құбырлы архитектураларда жоғары болатын тармақтарды дұрыс болжамаудың салдарынан туындайтын шығындарды жояды. Нұсқаулар жинағында нұсқаулар арқылы жасалған толық жағдай кодтары болған жағдайда, жағдай тізілімдерін тікелей пайдалану арқылы немесе болжам ретінде қолдану арқылы кодтың көлемін одан әрі қысқартуға болады.
Functions that are traditionally computed using simple arithmetic and bitwise operations may be quicker to compute using predicated instructions. Predicated instructions with different predicates can be mixed with each other and with unconditional code, allowing better instruction scheduling and so even better performance. Elimination of unnecessary branch instructions can make the execution of necessary branches, such as those that make up loops, faster by lessening the load on branch prediction mechanisms. Elimination of the cost of a branch misprediction which can be high on deeply pipelined architectures. Instruction sets that have comprehensive Condition Codes generated by instructions may reduce code size further by directly using the Condition Registers in or as predication.
Кемшіліктер
Болжамның басты кемшілігі – кодтауға кететін жадтың көбеюі. Көбінесе, әрбір команда, оның қандай шарттарда орындалуын көрсететін болжамдық биттер жинағын пайдаланады. Егер жад көлемі шектеулі болса, мысалы, кіріктірілген құрылғыларда, бұл жадты үнемдеу қиынға түсуі мүмкін. Дегенмен, Thumb 2 сияқты кейбір архитектуралар мұндай мәселенің алдын алады (төменде қараңыз). Басқа да кемшіліктері бар: болжам аппараттық құрылымды күрделендіреді, өйткені оның ішкі логикасына қосымша деңгейлер енгізіледі, бұл процессордың жылдамдығын төмендетуі мүмкін. Болжамдық блок барлық операциялар үшін циклдарды қамтиды, сондықтан қысқа жолдар да ұзаққа созылып, уақытты қажет етеді. Болжам көбінесе алдын ала болжамайды және ұзақ тәуелділік тізбегін құрайды. Реттелген деректер үшін бұл болжамды тармақтан гөрі нашар өнімділікке алып келеді. Болжам жолдардың теңдес болғанда немесе ең ұзақ жол ең көп орындалғанда тиімді, бірақ мұндай жолды анықтау компиляция кезінде, тіпті профильдеу деректері болған жағдайда да өте қиын.
Predication complicates the hardware by adding levels of logic to critical paths and potentially degrades clock speed. A predicated block includes cycles for all operations, so shorter paths may take longer and be penalized. Predication is not usually speculated and causes a longer dependency chain. For ordered data this translates to a performance loss compared to a predictable branch. Predication is most effective when paths are balanced or when the longest path is the most frequently executed, but determining such a path is very difficult at compile time, even in the presence of profiling information.
Тарих
Болжалған нұсқаулар 1950-ші жылдардағы еуропалық компьютерлік жобаларда, соның ішінде Mailüfterl (1955), Zuse Z22 (1955), ZEBRA (1958) және Electrologica X1 (1958) танымал болды. 1967 жылғы IBM ACS 1 дизайны өзінің нұсқаулық форматтарында "өткізу" (skip) бітін қолданды, ал 1976 жылғы CDC икемді процессоры өзінің микронұсқаулық форматтарында үш шартты орындалу бітін бөлді. Hewlett Packard-тың PA RISC архитектурасында (1986) nullification деп аталатын мүмкіндік болды, ол көптеген нұсқауларды алдыңғы нұсқауға байланысты етуге мүмкіндік берді. IBM-нің POWER архитектурасы (1990) шартты жылжыту нұсқауларын енгізді. POWER-дің ізбасары PowerPC (1993) бұл нұсқаулардан бас тартты. Digital Equipment Corporation компаниясының Alpha архитектурасы (1992) да шартты жылжыту нұсқауларын қамтыды. MIPS 1994 жылы MIPS IV нұсқасымен шартты жылжыту нұсқауларын алды; ал SPARC 9 (1994) нұсқасында бүтін сандар мен қозғалатын нүктелер тіркелімдері үшін шартты жылжыту нұсқауларымен толықтырылды. Hewlett Packard/Intel IA 64 архитектурасында көптеген нұсқаулар шартты түрде орындалады. Шарттар 64 арнайы мақсаттағы шарт тіркелімдерінде сақталады; және шарт тіркелімдерінің бірі әрқашан рас болып табылады, сондықтан шартсыз нұсқаулар тек "рас" мәнімен шартталған нұсқаулар болып табылады. Шартты орындау IA 64 архитектурасында бағдарламалық құбыржолдарды іске асыру үшін маңызды, себебі ол прологтар мен эпилогтар үшін жеке код жазу қажеттілігін жояды. x86 архитектурасында Intel Pentium Pro (1995) процессорымен шартты жылжыту нұсқаулары (CMOV және FCMOV) отбасы қосылды. CMOV нұсқаулары бастапқы тіркелімнің мазмұнын межелі тіркелімге көшіреді, бұл тіркелімнің мәнімен берілген шартқа байланысты. ARM архитектурасында бастапқы 32 биттік нұсқаулар жиынтығы шартты орындау мүмкіндігін ұсынады, бұл көптеген нұсқауларды алдыңғы нұсқауда орнатылған төрт жағдай кодының комбинациясына негізделген 13 шарттың бірімен шарттауға мүмкіндік береді. ARM Thumb нұсқаулар жиынтығы (1994) нұсқаулардың өлшемін азайту үшін шартты орындаудан бас тартты, осылайша оларды 16 битке сыйғызуға болатын болды, бірақ оның ізбасары Thumb 2 (2003) бұл мәселені арнайы нұсқауды пайдалану арқылы шешті, ол келесі төрт нұсқау үшін шарттарды беруден басқа ешқандай әсер етпейді. ARMv8 A (2011) архитектурасында енгізілген 64 биттік нұсқаулар жиынтығы шартты орындауды шартты таңдау нұсқауларымен алмастырды.
SIMD, SIMT және векторлық болжау
Кейбір SIMD нұсқаулық жиынтықтары, мысалы AVX2, логикалық масканы пайдаланып жадқа мәндерді шартты түрде жүктеу/сақтау мүмкіндігіне ие, бұл шартты жылжудың параллель түрі. Сонымен қатар, олар параллель операцияны орындайтын жеке арифметикалық бірліктерге жеке маска биттерін қолдануы мүмкін. Бұл техника Флинннің таксономиясында "ассоциативтік өңдеу" деп белгіленеді. Осы түрдегі шартты орындау векторлық процессорларда және бір нұсқаулық, көп жіпті GPU есептеулерінде де қолданылады. Бір скалярлық шартты орындаудың барлық әдістері, артықшылықтары мен кемшіліктері параллель өңдеу жағдайына да толыққанды қолданылады.