Алгоритмдердің тиімділігі және ресурстарды пайдалану

Кіріспе

Алгоритмнің қасиеттері

Компьютерлік ғылымда алгоритмдік тиімділік – алгоритм қолданатын есептеу ресурстарының мөлшерімен байланысты алгоритмнің қасиеті. Алгоритмдік тиімділікті қайталанатын немесе үздіксіз процеске арналған инженерлік өнімділікке ұқсас деп қарастыруға болады. Ең жоғары тиімділікке қол жеткізу үшін ресурстарды азайту қажет. Дегенмен, уақыт және кеңістік сияқты әртүрлі ресурстарды тікелей салыстыру мүмкін емес, сондықтан екі алгоритмнің қайсысы тиімдірек саналатыны көбінесе тиімділіктің қай өлшемі маңыздырақ екеніне байланысты. Мысалы, көпіршік сұрыптау (bubble sort) және тимсұрыптау (timsort) екеуі де элементтер тізімін кішіден үлкенге қарай сұрыптауға арналған алгоритмдер. Көпіршік сұрыптау тізімді элементтер санының квадратына пропорционалды уақытта сұрыптайды (Big O нотациясын қараңыз), бірақ тізімнің ұзындығына тәуелді тұрақты мөлшердегі қосымша жадты ғана қажет етеді. Тимсұрыптау тізімді тізімнің ұзындығына сызықтық-логарифмдік уақытта (саны мен оның логарифмінің көбейтіндісіне пропорционалды) сұрыптайды, бірақ тізімнің ұзындығына сызықтық кеңістік талап етеді. Егер белгілі бір қолданба үшін үлкен тізімдерді жоғары жылдамдықпен сұрыптау қажет болса, тимсұрыптау жақсы таңдау болады; алайда, егер сұрыптаудың жадты пайдалануын азайту маңыздырақ болса, көпіршік сұрыптау жақсырақ болады.

Шолу

Алгоритм тиімді деп есептеледі, егер оның ресурстарды тұтынуы, яғни есептеу шығындары, белгілі бір қабылданатын деңгейде немесе одан төмен болса. Шамамен айтқанда, «қабылданатын» дегеніміз – ол қолданыстағы компьютерде ақылға қонымды уақыт ішінде немесе жад көлемінде, әдетте кіріс деректің мөлшеріне байланысты жұмыс істеуі керек. 1950 жылдан бері компьютерлердің есептеу қуаты мен жад көлемі күрт өсті, сондықтан қазіргі қабылданатын деңгейлер 10 жыл бұрын қабылдауға болмас еді. Шындығында, компьютерлік қуаттың шамамен екі жыл сайын екі есеге ұлғаюының арқасында, қазіргі заманғы смартфондар мен кіріктірілген жүйелерде тиімді жұмыс істейтін тапсырмалар, 10 жыл бұрын өнеркәсіптік серверлер үшін тиімсіз болуы мүмкін. Компьютер өндірушілер жиі жаңа үлгілерді шығарады, көбінесе олар жоғары өнімділікке ие. Бағдарламалық жасақтаманың құны жоғары болуы мүмкін, сондықтан кейбір жағдайларда өнімділікті арттырудың ең оңай және арзан жолы – егер ол қолданыстағы компьютермен үйлесімді болса, жылдам компьютер сатып алу. Алгоритм қолданатын ресурстарды өлшеудің көптеген тәсілдері бар: ең көп қолданылатыны – жылдамдық және жадты пайдалану; басқа өлшемдерге деректерді беру жылдамдығы, уақытша дискіні пайдалану, ұзақ мерзімді дискіні пайдалану, қуатты тұтыну, меншік құны, сыртқы факторларға жауап беру уақыты және т.б. кіреді. Бұл өлшемдердің көпшілігі алгоритмге берілген деректердің мөлшеріне, яғни өңделетін деректердің көлеміне байланысты. Олар деректердің орналасу тәсіліне де байланысты болуы мүмкін; мысалы, кейбір сұрыптау алгоритмдері бұрыннан сұрыпталған немесе кері сұрыпталған деректермен нашар жұмыс істейді. Іс жүзінде алгоритмнің тиімділігіне әсер ететін басқа да факторлар бар, мысалы, қажетті дәлдік және/немесе сенімділік. Төменде егжей-тегжейлі көрсетілгендей, алгоритмді іске асыру тәсілі де нақты тиімділікке маңызды әсер ете алады, бірақ оның көптеген аспектілері оңтайландыру мәселелерімен байланысты.

Орындау мәселесі

Іске асыру мәселелері тиімділікке әсер етуі мүмкін, мысалы, бағдарламалау тілін таңдау, алгоритмнің нақты кодталу тәсілі, немесе белгілі бір тіл үшін компиляторды таңдау, немесе компиляция параметрлерінің қолданылуы, тіпті пайдаланылатын операциялық жүйе. Көп жағдайда интерпретатормен іске асырылған тіл, компилятормен іске асырылған тілден әлдеқайда баяу болуы мүмкін. "Дереу компиляция" және "интерпретацияланған тілдер" туралы мақалаларды қараңыз. Уақыт немесе жадқа қатысты мәселелерге әсер ететін, бірақ бағдарламашының бақылауынан тыс факторлар да бар; оларға деректердің туралануы, деректердің гранулярлығы, кэш жақындығы, кэш сәйкестігі, қоқыс жинау, нұсқау деңгейіндегі параллелизм, көп жіптілік (жабдық немесе бағдарламалық деңгейде), бір уақытта бірнеше тапсырманы орындау және кіші бағдарлама шақырулары кіреді. Кейбір процессорларда векторлық өңдеу мүмкіндігі бар, бұл бір нұсқаудың бірнеше операторда жұмыс істеуіне мүмкіндік береді; бағдарламашы немесе компилятор үшін осы мүмкіндікті пайдалану оңай немесе қиын болуы мүмкін. Тізбекті өңдеуге арналған алгоритмдерді параллель өңдеуді пайдалану үшін толығымен қайта жобалау қажет болуы мүмкін немесе оларды оңай қайта конфигурациялауға болады. Параллель және үлестірілген есептеулер 2010 жылдардың соңында маңыздылығы артып келе жатқандықтан, CUDA, TensorFlow, Hadoop, OpenMP және MPI сияқты параллель және үлестірілген есептеу жүйелері үшін тиімді жоғары деңгейдегі API-лерге көбірек инвестициялар жасалуда. Бағдарламалау кезінде туындауы мүмкін тағы бір мәселе – бірдей нұсқаулар жиынтығымен (мысалы, x86 64 немесе ARM) үйлесімді процессорлар нұсқауларды әртүрлі тәсілдермен іске асыруы мүмкін, сондықтан кейбір модельдерде жылдам нұсқаулар басқа модельдерде баяу болуы мүмкін. Бұл компиляторларды оңтайландыруға қиындық туғызады, олар бағдарламаны орындауды оңтайландыру үшін компиляция нысанындағы нақты CPU және басқа аппараттық жабдық туралы көп білуі керек. Ең нашар жағдайда, компилятор компиляция нысанында қолдау көрсетілмейтін нұсқауларды эмуляциялауға мәжбүр болуы мүмкін, нәтижесінде кодты жасауға немесе сыртқы кітапхананы шақыруға тура келеді, бұл нәтиже сол платформада есептелуі мүмкін емес, тіпті басқа платформаларда аппараттық деңгейде қолдау көрсетілсе де және тиімдірек болса да. Бұл көбінесе кіріктірілген жүйелерде қалқыма нүктелі арифметикаға қатысты, онда кішкентай және аз қуатты микроконтроллерлер көбінесе қалқыма нүктелі арифметика үшін аппараттық қолдауға ие болмайды және осылайша қалқыма нүктелі есептеулерді жасау үшін есептеу жағынан қымбат бағдарламалық процедураларды қажет етеді.

Implementation issues can also have an effect on efficiency, such as the choice of programming language, or the way in which the algorithm is actually coded, or the choice of a compiler for a particular language, or the compilation options used, or even the operating system being used. In many cases a language implemented by an interpreter may be much slower than a language implemented by a compiler. See the articles on just in time compilation and interpreted languages. There are other factors which may affect time or space issues, but which may be outside of a programmer's control; these include data alignment, data granularity, cache locality, cache coherency, garbage collection, instruction level parallelism, multi threading (at either a hardware or software level), simultaneous multitasking, and subroutine calls. Some processors have capabilities for vector processing, which allow a single instruction to operate on multiple operands; it may or may not be easy for a programmer or compiler to use these capabilities. Algorithms designed for sequential processing may need to be completely redesigned to make use of parallel processing, or they could be easily reconfigured. As parallel and distributed computing grow in importance in the late 2010s, more investments are being made into efficient high level APIs for parallel and distributed computing systems such as CUDA, TensorFlow, Hadoop, OpenMP and MPI. Another problem which can arise in programming is that processors compatible with the same instruction set (such as x86 64 or ARM) may implement an instruction in different ways, so that instructions which are relatively fast on some models may be relatively slow on other models. This often presents challenges to optimizing compilers, which must have a great amount of knowledge of the specific CPU and other hardware available on the compilation target to best optimize a program for performance. In the extreme case, a compiler may be forced to emulate instructions not supported on a compilation target platform, forcing it to generate code or link an external library call to produce a result that is otherwise incomputable on that platform, even if it is natively supported and more efficient in hardware on other platforms. This is often the case in embedded systems with respect to floating point arithmetic, where small and low power microcontrollers often lack hardware support for floating point arithmetic and thus require computationally expensive software routines to produce floating point calculations.

Теория

Алгоритмді талдау, әдетте кіріс деректерінің мөлшеріне қатысты орындалу уақытын бағалау үшін уақыт күрделілігін талдау арқылы жасалады. Нәтижесі көбінесе Big O нотациясымен көрсетіледі. Бұл, әсіресе көп мөлшердегі деректерді өңдеу қажет болғанда, алгоритмдерді салыстыруға көмектеседі. Деректердің мөлшері шағын болғанда алгоритмдердің тиімділігін салыстыру үшін нақтырақ бағалаулар қажет, бірақ мұның маңыздылығы төмен болуы мүмкін. Параллель өңдеуді қолданатын алгоритмдерді талдау қиынға түсуі мүмкін.

Практика

Алгоритмді қолдану уақытын өлшеу үшін эталонды пайдаланыңыз. Көптеген бағдарламалау тілдерінде процессор уақытын пайдалануды анықтайтын қолжетімді функция бар. Ұзаққа созылатын алгоритмдер үшін өткен уақыт та маңызды болуы мүмкін. Нәтижелерді әдетте бірнеше сынақтардың орташа мәні бойынша есептеу керек. Орындау кезіндегі профильдеу аппараттық конфигурацияға және көп өңдеулі және көп бағдарламалау ортасында басқа бағдарламалардың немесе тапсырмалардың бір уақытта жұмыс істеу мүмкіндігіне өте сезімтал болуы мүмкін. Мұндай сынақтардың нәтижелері бағдарламалау тілін, компиляторды және компилятор опцияларын таңдауға байланысты, сондықтан салыстырылатын алгоритмдердің бәрі бірдей жағдайларда жүзеге асырылуы тиіс.

Кэштеу және жад иерархиясы

Қазіргі компьютерлерде салыстырмалы түрде көп жад (мысалы, гигабайттар) болуы мүмкін, сондықтан алгоритмді шектеулі жадқа сығымдау бұрынғыдан гөрі әлдеқайда аз мәселе тудырады. Бірақ жадтың төрт түрлі санаттарының болуы маңызды болуы мүмкін: Процессор тіркегіштері – компьютер жады технологиясының ең жылдам түрі, ең аз сақтау кеңістігімен. Қазіргі заманғы компьютерлерде тікелей есептеулер көбінесе қажет болған жағдайда кэшке, негізгі жадқа және виртуалды жадқа жаңартылмас бұрын, бастапқы және мақсатты операторлармен тіркегіштерде жүргізіледі. Процессорлық ядрода әдетте жүздеген байттан кем немесе одан аз тіркегіштер болады, бірақ тіркегіштік файлда нұсқаулар жиынтығы архитектурасында анықталған архитектуралық тіркегіштерге қарағанда физикалық тіркегіштер көп болуы мүмкін. Кэш жады – жад иерархиясында екінші ең жылдам және екінші ең кішкентай жад. Кэштер CPU, GPU, қатты дискілерде және сыртқы перифериялық құрылғыларда кездеседі және әдетте статикалық жадта (RAM) іске асырылады. Жады кэштері көп деңгейлі болады; төменгі деңгейлер үлкен, баяу және әдетте көп ядролы процессорларда процессорлық ядролар арасында бөліседі. Кэш жадындағы операторларды өңдеу үшін, өңдеу блогы кэштен деректерді алуы, операцияны тіркегіштерде орындауы және деректерді кэшке қайта жазуы керек. Бұл L1 кэшінде болса, CPU немесе GPU арифметикалық-логикалық құрылмысымен немесе қозғалатын нүктелік құрылмысымен салыстырылатын жылдамдықпен (шамамен 2-10 есе баяу) жұмыс істейді. Егер L1 кэштен қате туса, дерек L2 кэштен алынып, оған жазылуы керек, ал L2 кэштен қате туса, дерек L3 кэштен алынып, оған жазылуы керек (егер ол болса), бұл 10 есе баяу. Негізгі физикалық жад көбінесе динамикалық жадта (DRAM) іске асырылады. Негізгі жад L3 CPU кэшінен әлдеқайда үлкен (әдетте ≈8 мегабайтқа қарағанда гигабайттар) және оқу мен жазу уақыты әдетте 10-100 есе баяу. 2018 жылдан бастап RAM процессорлардың чипінде, CPU немесе GPU жады ретінде көбірек іске асырылуда. Виртуалды жад көбінесе қатты дискі сияқты қосымша жад сақтағышы ретінде іске асырылады және жад иерархиясының кеңейтілуі болып табылады, ол әлдеқайда үлкен сақтау кеңістігіне ие, бірақ әлдеқайда үлкен уақыт кешігуіне (RAM-дегі мән үшін кэштен қатеге қарағанда әдетте 1000 есе баяу) ие. Алғашында қол жетімді болғаннан гөрі көп жад бар деген әсерді тудыру үшін ынталандырылған болса да, виртуалды жад қазіргі уақытта уақыт-кеңістік арақатынасы үшін және виртуалды машиналарды пайдалануға мүмкіндік беру үшін маңызды. Негізгі жадтан кэштен қате туса, ол беттік қате деп аталады және бағдарламалардың өнімділігіне үлкен зиян келтіреді. Жадының қажеттіліктері кэш жадына сыятын алгоритм, негізгі жадқа сыятын алгоритмге қарағанда әлдеқайда жылдам болады, ал ол өз кезегінде виртуалды жадқа жүгінуге мәжбүр болатын алгоритмге қарағанда әлдеқайда жылдам болады. Осы себепті кэшті алмастыру саясаты жоғары өнімді есептеу үшін өте маңызды, сондай-ақ кэшті сезінетін бағдарламалау және деректерді туралау да маңызды. Мәселені одан әрі күрделілендіру үшін кейбір жүйелерде кэш жадының үш деңгейі бар, олардың әрқайсысының тиімді жылдамдығы әртүрлі. Әр түрлі жүйелерде осы жад түрлерінің әртүрлі мөлшері болуы мүмкін, сондықтан алгоритмнің жад қажеттіліктерінің әсері бір жүйеден екіншісіне қатты өзгеруі мүмкін. Электрондық есептеудің алғашқы күндерінде, егер алгоритм мен оның деректері негізгі жадқа сыймаса, онда алгоритмді пайдалану мүмкін болмады. Бүгінгі таңда виртуалды жадтың қолданылуы көп жадты қамтамасыз етеді, бірақ бұл өнімділіктің төмендеуіне әкеледі. Егер алгоритм мен оның деректері кэш жадына сыятын болса, онда өте жоғары жылдамдыққа қол жеткізуге болады; бұл жағдайда кеңістікті азайту уақытты азайтуға да көмектеседі. Бұл жергілікті принцип деп аталады және оны анықтамалық жергіліктілік, кеңістіктік жергіліктілік және уақытша жергіліктілік деп бөлуге болады. Кэш жадына толық сыймайтын, бірақ анықтамалық жергіліктілікті көрсететін алгоритм жақсы жұмыс істей алады.

Current computers can have relatively large amounts of memory (possibly Gigabytes), so having to squeeze an algorithm into a confined amount of memory is much less of a problem than it used to be. But the presence of four different categories of memory can be significant:

Processor registers, the fastest of computer memory technologies with the least amount of storage space. Most direct computation on modern computers occurs with source and destination operands in registers before being updated to the cache, main memory and virtual memory if needed. On a processor core, there are typically on the order of hundreds of bytes or fewer of register availability, although a register file may contain more physical registers than architectural registers defined in the instruction set architecture. Cache memory is the second fastest and second smallest memory available in the memory hierarchy. Caches are present in CPUs, GPUs, hard disk drives and external peripherals, and are typically implemented in static RAM. Memory caches are multi leveled; lower levels are larger, slower and typically shared between processor cores in multi core processors. In order to process operands in cache memory, a processing unit must fetch the data from the cache, perform the operation in registers and write the data back to the cache. This operates at speeds comparable (about 2 10 times slower) with the CPU or GPU's arithmetic logic unit or floating point unit if in the L1 cache. It is about 10 times slower if there is an L1 cache miss and it must be retrieved from and written to the L2 cache, and a further 10 times slower if there is an L2 cache miss and it must be retrieved from an L3 cache, if present. Main physical memory is most often implemented in dynamic RAM (DRAM). The main memory is much larger (typically gigabytes compared to ≈8 megabytes) than an L3 CPU cache, with read and write latencies typically 10 100 times slower. as of 2018, RAM is increasingly implemented on chip of processors, as CPU or GPU memory. Virtual memory is most often implemented in terms of secondary storage such as a hard disk, and is an extension to the memory hierarchy that has much larger storage space but much larger latency, typically around 1000 times slower than a cache miss for a value in RAM. While originally motivated to create the impression of higher amounts of memory being available than were truly available, virtual memory is more important in contemporary usage for its time space tradeoff and enabling the usage of virtual machines. Cache misses from main memory are called page faults, and incur huge performance penalties on programs. An algorithm whose memory needs will fit in cache memory will be much faster than an algorithm which fits in main memory, which in turn will be very much faster than an algorithm which has to resort to virtual memory. Because of this, cache replacement policies are extremely important to high performance computing, as are cache aware programming and data alignment. To further complicate the issue, some systems have up to three levels of cache memory, with varying effective speeds. Different systems will have different amounts of these various types of memory, so the effect of algorithm memory needs can vary greatly from one system to another. In the early days of electronic computing, if an algorithm and its data would not fit in main memory then the algorithm could not be used. Nowadays the use of virtual memory appears to provide much memory, but at the cost of performance. If an algorithm and its data will fit in cache memory, then very high speed can be obtained; in this case minimizing space will also help minimize time. This is called the principle of locality, and can be subdivided into locality of reference, spatial locality and temporal locality. An algorithm which will not fit completely in cache memory but which exhibits locality of reference may perform reasonably well.