Параллелдік алгоритмдер және олардың ерекшеліктері
Parallel algorithm
Параллелдік алгоритмдер: анықтамасы, түрлері, PRAM моделі. Қатар операцияларды орындау арқылы есептеу тиімділігін арттыру жолдары. Компьютер ғылымындағы маңызды түсінік.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Компьютерлік ғылымда қатарлы алгоритм, дәстүрлі тізбекті алгоритмге қарама-қарсы, белгілі бір уақытта бірнеше операцияны орындай алатын алгоритм болып табылады. Компьютерлік ғылымда тізбекті алгоритмдерді абстрактілі машина модельдерінде сипаттау қалыпты жағдай, көбінесе ол кездейсоқ кіруге болатын машина (RAM) деп аталады. Сол сияқты, көптеген компьютерлік ғылым зерттеушілері параллель кездейсоқ кіруге болатын машинаны (PRAM) параллель абстрактілі машина (ортақ жад) ретінде пайдаланған. Көптеген қатарлы алгоритмдер бір уақытта орындалады – бірақ, әдетте, бір уақытта орындалатын алгоритмдер жеке ұғым болып табылады – сондықтан бұл ұғымдар көбінесе шатастырылады, алгоритмнің қай бөлігі қатарлы, ал қайсысы бір уақытта орындалатыны нақты айқындалмайды. Бұдан бөлек, қатарлы да, бір уақытта орындалатын да емес алгоритмдер, бір уақытта орындалатын алгоритмдерге қарама-қарсы "тізбекті алгоритмдер" деп аталады.
In computer science, a parallel algorithm, as opposed to a traditional serial algorithm, is an algorithm which can do multiple operations in a given time. It has been a tradition of computer science to describe serial algorithms in abstract machine models, often the one known as random access machine. Similarly, many computer science researchers have used a so called parallel random access machine (PRAM) as a parallel abstract machine (shared memory). Many parallel algorithms are executed concurrently – though in general concurrent algorithms are a distinct concept – and thus these concepts are often conflated, with which aspect of an algorithm is parallel and which is concurrent not being clearly distinguished. Further, non parallel, non concurrent algorithms are often referred to as "sequential algorithms", by contrast with concurrent algorithms.
Паралельдеу мүмкіндігі
Алгоритмдердің параллельдеуге болатын деңгейі әртүрлі, оңай параллельдеуге болатындардан толығымен параллельдеуге келмейтіндерге дейін. Сонымен қатар, бір мәселені шешу үшін әртүрлі алгоритмдер қолданылуы мүмкін, олардың параллельдеу мүмкіндігі де әртүрлі болуы мүмкін. Кейбір мәселелерді осылай бөліктерге бөлу оңай – мұндайларын "өте оңай параллельдеуге болатын" мәселелер деп атайды. Мысалы, Рубик кубын шешуге арналған көптеген алгоритмдер мен белгілі бір хэш нәтижесін беретін мәндерді табу алгоритмдерін осыған жатқызуға болады. Ал кейбір мәселелерді параллель бөліктерге бөлу мүмкін емес, себебі олар келесі қадамды тиімді орындау үшін алдыңғы қадамның нәтижелерін қажет етеді. Мұндай мәселелерді "негізінен тізбекті" мәселелер деп атайды. Мысалдарға Ньютон әдісі сияқты итеративтік сандық әдістер, үш денелік мәселенің итеративтік шешімдері және пи (π) санын есептеуге қолданылатын көптеген алгоритмдер жатады. Кейбір тізбекті алгоритмдерді автоматты параллельдеу арқылы параллель алгоритмдерге түрлендіруге болады.
Algorithms vary significantly in how parallelizable they are, ranging from easily parallelizable to completely unparallelizable. Further, a given problem may accommodate different algorithms, which may be more or less parallelizable. Some problems are easy to divide up into pieces in this way – these are called embarrassingly parallel problems. Examples include many algorithms to solve Rubik's Cubes and find values which result in a given hash. Some problems cannot be split up into parallel portions, as they require the results from a preceding step to effectively carry on with the next step – these are called inherently serial problems. Examples include iterative numerical methods, such as Newton's method, iterative solutions to the three body problem, and most of the available algorithms to compute pi (π). Some sequential algorithms can be converted into parallel algorithms using automatic parallelization.
Мотивация
Жеке құрылғылардағы параллель алгоритмдер 2000-шы жылдардың басынан бері мультипроцессорлық жүйелердің және көп ядролы процессорлардың дамуына байланысты жиі қолданылатын болды. 2004 жылдың соңына дейін бір ядролы процессордың өнімділігі жиіліктің артуы арқылы қарқынды өсті, сондықтан бірдей өнімділікке ие көп баяу ядролы компьютерге қарағанда, бір жылдам ядролы компьютер құрастыру оңайырақ болды, демек көп ядролы жүйелердің пайдасы шектеулі болды. Бірақ 2004 жылдан бастап жиіліктің артуы тоқтап, көп ядролы жүйелер кеңінен таралып, параллель алгоритмдерді жалпы қолданысқа енгізді.
Parallel algorithms on individual devices have become more common since the early 2000s because of substantial improvements in multiprocessing systems and the rise of multi core processors. Up until the end of 2004, single core processor performance rapidly increased via frequency scaling, and thus it was easier to construct a computer with a single fast core than one with many slower cores with the same throughput, so multicore systems were of more limited use. Since 2004 however, frequency scaling hit a wall, and thus multicore systems have become more widespread, making parallel algorithms of more general use.
Байланыс
Серілік алгоритмдердің құны немесе күрделілігі олардың алатын жады (кеңістік) және уақыт (процессор циклдары) арқылы бағаланады. Параллель алгоритмдер тағы бір ресурсты – әртүрлі процессорлар арасындағы байланысты оңтайландыруы керек. Параллель процессорлар екі тәсілмен байланысады: ортақ жад арқылы немесе хабар алмасу арқылы. Ортақ жадты пайдалану деректерді қосымша құлыптауды қажет етеді, процессор мен шина циклдарына қосымша жүктеме салады, сондай-ақ алгоритмнің бір бөлігін тізбектей орындауға мәжбүрлейді. Хабар алмасу арналар мен хабарлық қораптарды пайдаланады, бірақ бұл байланыс шинада деректерді жіберуге қосымша шығын, кезектер мен хабарлық қораптарға қосымша жад қажеттілігі және хабарламалардағы кешігуді тудырады. Параллель процессорлардың дизайнында арнайы шиналар, мысалы, кроссбар шинасы қолданылады, осылайша байланыс жүктемесін азайтуға болады, бірақ трафик көлемін паралель алгоритм анықтайды. Егер қосымша процессорлардың байланыс шығыны, қосымша процессорды қосудан алынған пайдадан басып кетсе, параллель өнімділік төмендеуіне келіп соғады.
The cost or complexity of serial algorithms is estimated in terms of the space (memory) and time (processor cycles) that they take. Parallel algorithms need to optimize one more resource, the communication between different processors. There are two ways parallel processors communicate, shared memory or message passing. Shared memory processing needs additional locking for the data, imposes the overhead of additional processor and bus cycles, and also serializes some portion of the algorithm. Message passing processing uses channels and message boxes but this communication adds transfer overhead on the bus, additional memory need for queues and message boxes and latency in the messages. Designs of parallel processors use special buses like crossbar so that the communication overhead will be small but it is the parallel algorithm that decides the volume of the traffic. If the communication overhead of additional processors outweighs the benefit of adding another processor, one encounters parallel slowdown.
Жүк тепе-теңдігін сақтау
Паралель алгоритмдермен байланысты тағы бір мәселе – олардың тиімді жүктеме теңгерімін қамтамасыз ету, яғни кіріс мөлшерін теңгерімдеудің орнына, жүктеменің (жалпы жұмыстың) теңгерімді болуын қадағалау. Мысалы, бірден жүз мыңға дейінгі сандарды жай сан екенін анықтау процессорлар арасында оңай бөліседі; бірақ, егер сандар тең бөлінсе (1–1000, 1001–2000, және т.б.), жұмыс көлемі теңгерімсіз болады, себебі кішірек сандарды осы алгоритммен өңдеу оңай (жай сан екенін тексеру оңай), сондықтан кейбір процессорлар басқаларына қарағанда көп жұмыс істейді, ал қалғандары жүктеме алған процессорлар жұмысын аяқтағанға дейін бос күйінде тұрады.
Another problem with parallel algorithms is ensuring that they are suitably load balanced, by ensuring that load (overall work) is balanced, rather than input size being balanced. For example, checking all numbers from one to a hundred thousand for primality is easy to split among processors; however, if the numbers are simply divided out evenly (1–1,000, 1,001–2,000, etc. ), the amount of work will be unbalanced, as smaller numbers are easier to process by this algorithm (easier to test for primality), and thus some processors will get more work to do than the others, which will sit idle until the loaded processors complete.
Таратылған алгоритмдер
Параллель алгоритмдердің бір түрі – үлестірілген алгоритмдер – кластерлік және үлестірілген есептеу орталарында жұмыс істеу үшін жасалған алгоритмдер. Бұл орталарда "классикалық" параллель алгоритмдерде қарастырылмаған қосымша мәселелерді шешу қажет.
A subtype of parallel algorithms, distributed algorithms, are algorithms designed to work in cluster computing and distributed computing environments, where additional concerns beyond the scope of "classical" parallel algorithms need to be addressed.