Бағдарламалық параллелизмді іске асыру тәсілі

Кіріспе

Паралельдікке қол жеткізу үшін қолданылатын есептеу техникасы

Есептеуде, бір бағдарлама, көп дерек (SPMD) – бірнеше процессорлар бағдарламаны орындау кезінде нәтижелерді жылдам алу үшін ынтымақтаса жұмыс істейтін параллельдікті пайдалануға арналған есептеу модельдерін білдіретін термин. SPMD термині 1983 жылы енгізілді және екі түрлі есептеу моделін көрсету үшін қолданылды:

Мишель Огуэн (Ницца университеті София Антиполис) және Франсуа Ларби (Томсон/Синтра) тарапынан, "бөліп орындау" және деректер параллельді тәсіл ретінде, онда параллельді тапсырмалар ("бір бағдарлама") бөлініп, әртүрлі кіріс деректері бар бірнеше SIMD процессорларында бір уақытта синхронды түрде орындалады, және
Фредерика Дарема (IBM) тарапынан, онда барлық (процессорлар) процестер бір бағдарламаны орындауды бастайды, бірақ синхрондау директивалары арқылы әртүрлі нұсқауларды орындауға және әртүрлі деректермен жұмыс істеуге өздігінен жоспарлайды, сондай-ақ берілген бағдарламаның MIMD параллельділігін қамтамасыз етеді, бұл деректер параллельділігінен гөрі жалпылама тәсіл және жалпы мақсаттағы көппроцессорларда параллельді орындау үшін "бөліп орындау" тәсілінен тиімді. (IBM) SPMD – параллельді бағдарламалаудың ең көп таралған стилі және берілген ("бір") бағдарламаның MIMD орындалуымен байланысты болғандықтан, оны MIMD-дің кіші түрі деп қарастыруға болады. Бұл сонымен қатар белсенді хабарламалар және бөлінген жад сияқты зерттеу концепцияларының қажетті шарты болып табылады.

SPMD және SIMD

SPMD параллель орындалуында, бірнеше автономды процессорлар SIMD немесе SIMT-тың әртүрлі деректерге қатысты синхронды түрде орындау қағидасынан өзгеше, тәуелсіз нүктелерде бірдей бағдарламаны бір мезгілде орындайды. SPMD арқылы тапсырмаларды жалпы мақсаттағы процессорларда орындауға болады. SIMD-де деректер ағындарын өңдеу үшін бір операция (нұсқау) бірнеше дерекке қолданылады (SIMD-дың бір түрі – векторлық өңдеу, онда деректер векторлар түрінде ұйымдастырылады). Процессорлардың тағы бір класы – GPU, бірнеше SIMD ағындарын өңдейді. SPMD және SIMD өзара қосаулы емес; SPMD параллель орындалуы SIMD, векторлық өңдеу немесе GPU-ның қосалқы өңдеуін қамтуы мүмкін. SPMD хабар алмасу және ортақ жадты архитектурада параллель бағдарламалау үшін қолданылған.

Бөлінген жады

Бөлінген жадты компьютерлік архитектураларда SPMD іске асырылымдары әдетте хабар алмасу бағдарламалауын қолданады. Бөлінген жадты компьютер – өзара байланысқан, тәуелсіз компьютерлер жиынтығынан тұрады, олар түйіндер деп аталады. Параллель орындау үшін әрбір түйін өз бағдарламасын іске қосады және басқа түйіндермен хабарларды жіберу және қабылдау арқылы байланысады, осы мақсатта жіберу/қабылдау процедураларын шақырады. Басқа параллельдеу директивалары, мысалы, кедергі синхрондау, хабарлар арқылы да іске асырылуы мүмкін. Хабарлар бірнеше байланыс механизмдері арқылы жіберіледі, мысалы, Ethernet арқылы TCP/IP немесе Myrinet және Supercomputer Interconnect сияқты арнайы жоғары жылдамдықты өзара байланыстар арқылы. Бөлінген жадты ортада бағдарламаның тізбекті бөлімдері бір түйінде нәтижені есептеу және оны басқаларына жіберудің орнына, барлық түйіндерде тізбекті бөлімді бірдей есептеу арқылы іске асырылуы мүмкін, егер бұл байланыс шығындарын азайту арқылы өнімділікті арттырса. Бүгінде бағдарламашы PVM және MPI сияқты стандартты интерфейстер арқылы хабар алмасудың егжей-тегжейінен оқшауланған. Бөлінген жад – үйде жасалған Beowulf кластерлерінен бастап Teragrid-тегі ең ірі кластерлерге дейін, сондай-ақ қазіргі GPU-негізделген суперкомпьютерлерде қолданылатын бағдарламалау стилі.

Ортақ жады

Ортақ жад машинасы (бірнеше өзара байланысты процессорлары бар және бірдей жад кеңістігіне қол жеткізетін компьютер) ішінде ортақ пайдалану физикалық ортақ жад немесе логикалық ортақ (бірақ физикалық түрде бөлінген) жад арқылы жүзеге асырылуы мүмкін. Ортақ жадтан өзге, компьютер жүйесіндегі процессорлар жергілікті (немесе жеке) жадты да қамтуы мүмкін. Мұндай жағдайларда, синхрондау аппараттық қолдауға ие примитивтермен (мысалы, салыстыру және алмастыру немесе алу және қосу) қамтамасыз етілуі мүмкін. Егер аппараттық қолдау болмаса, құлыптар қолданылуы мүмкін, ал деректер процессорлар (немесе жалпы алғанда, процестер немесе жіптер) арасында ортақ жад аймағына салынған деректерді алмастыру арқылы таратылуы мүмкін. Аппараттық жадты ортақ пайдалануды қолдамаса, деректерді «хабарлама» түрінде жинақтау, процессорлардың көп саны бар компьютерлерді (логикалық түрде) бағдарламалаудың тиімді жолы болып табылады, онда физикалық жад процессорларға тиесілі болады және басқа процессордың жадына қол жеткізу ұзаққа созылуы мүмкін. Ортақ жад машинасының SPMD-сі стандартты процестер (ауыр салмақты) немесе жіптер (жеңіл салмақты) арқылы іске асырылуы мүмкін. Ортақ жадты көппроцессорлық өңдеу (симметриялық көппроцессорлық өңдеу, SMP және біркелкі емес жадқа қол жеткізу, NUMA) бағдарламашыға ортақ жад кеңістігін және орындалуды параллельдеу мүмкіндігін ұсынады. (IBM) SPMD моделінде бірлесіп жұмыс істейтін процессорлар (немесе процестер) бағдарлама арқылы әртүрлі жолдармен өтеді, параллель директиваларды (параллельдеу және синхрондау директивалары, олар салыстыру және алмастыру, сондай-ақ ортақ жад синхрондау айнымалыларында алу және қосу операцияларын пайдалана алады) қолданады және ортақ жадтағы деректермен операциялар жасайды («ортақ деректер»); процессорлар (немесе процестер) сондай-ақ жергілікті жадтағы деректерге қол жеткізе алады және олармен операциялар жасайды («жеке деректер»). Ал, бұранда және біріктіру тәсілдерінде бағдарлама бір процессорда орындала бастайды және орындалу параллель аймақта бөлінеді, бұл параллель директивалар кездескенде басталады; параллель аймақта процессорлар әртүрлі деректерде параллель тапсырманы орындайды. Типтік мысал – параллель DO циклы, онда әртүрлі процессорлар циклға қатысатын массивтердің бөлек бөліктерімен жұмыс істейді. Цикл аяқталғаннан кейін орындалу синхрондалады (жұмсақ немесе қатты кедергілермен) – «параллель есептеуге қатысатын барлық процестер орындалудың басында құрылады және оның соңына дейін сақталады», (процессорлар/процестер) «әр түрлі нұсқауларды орындайды және әртүрлі деректермен әрекеттеседі», «әр процеске жүктелетін жұмыс (тапсырма) динамикалық түрде бөлінеді», яғни процестер «әр түрлі нұсқауларды орындау үшін және әртүрлі деректермен әрекеттесу үшін өздігінен жоспарлайды», осылайша бағдарламадағы қатар және параллель тапсырмаларды (сондай-ақ тапсырмаларды көшіруді) орындау үшін ынтымақтастыққа өздерін тағайындайды. Процесс түсінігі процессор терминінің жалпылама түрі ретінде қолданылды, себебі бірнеше процесс процессорда орындалуы мүмкін (мысалы, тиімділік пен жүктеме теңгерімділігі үшін үлкен дәрежеде параллелизмді пайдалану үшін). (IBM) SPMD моделі Darema тарапынан сол кездегі қауымдастықта барлық басқалар ұстанған бұранда және біріктіру тәсілінен өзгеше және тиімдірек тәсіл ретінде ұсынылды; ол «деректер параллельді» есептеу моделінен де жалпырақ және бұранда және біріктіруді қоса алады (ішкі санатты іске асыру ретінде). (IBM) SPMD-нің бастапқы контексі RP3 компьютері (512 процессорлық IBM Research Parallel Processor Prototype) болды, ол жалпы мақсаттағы есептеуді, сондай-ақ бөлінген және (логикалық) ортақ жадты қолдады. (IBM) SPMD-нің тиімділігі қосымшалардың кең класы үшін, параллель бағдарламалаудағы алғашқы өнімдік өнім ретінде, MPI (1991 жылдан бастап), OpenMP (1997 жылдан бастап) және (IBM) SPMD есептеу моделін қабылдаған және сілтеме жасайтын басқа орталарда көрсетілді. 1980 жылдардың соңында көптеген бөлінген компьютерлер мен меншіккілік хабар алмасу кітапханалары пайда болды. SPMD-нің алғашқы стандарты PVM болды. Қазіргі де-факто стандарты MPI болып табылады. Cray параллельдік директивалары OpenMP-нің тікелей алдын бағыттары болды.

On a shared memory machine (a computer with several interconnected CPUs that access the same memory space), the sharing can be implemented in the context of either physically shared memory or logically shared (but physically distributed) memory; in addition to the shared memory, the CPUs in the computer system can also include local (or private) memory. For either of these contexts, synchronization can be enabled with hardware enabled primitives (such as compare and swap, or fetch and add. For machines that do not have such hardware support, locks can be used and data can be “exchanged” across processors (or, more generally, processes or threads) by depositing the sharable data in a shared memory area. When the hardware does not support shared memory, packing the data as a “message” is often the most efficient way to program (logically) shared memory computers with large number of processors, where the physical memory is local to processors and accessing memory of another processor takes longer. SPMD on a shared memory machine can be implemented by standard processes (heavyweight) or threads (lightweight). Shared memory multiprocessing (both symmetric multiprocessing, SMP, and non uniform memory access, NUMA) presents the programmer with a common memory space and the possibility to parallelize execution. With the (IBM) SPMD model the cooperating processors (or processes) take different paths through the program, using parallel directives (parallelization and synchronization directives, which can utilize compare and swap and fetch and add operations on shared memory synchronization variables), and perform operations on data in the shared memory (“shared data”); the processors (or processes) can also have access and perform operations on data in their local memory (“private data”). In distinction, with fork and join approaches, the program starts executing on one processor and the execution splits in a parallel region, which is started when parallel directives are encountered; in a parallel region, the processors execute a parallel task on different data. A typical example is the parallel DO loop, where different processors work on separate parts of the arrays involved in the loop. At the end of the loop, execution is synchronized (with soft or hard barriers “all processes participating in the parallel computation are created at the beginning of the execution and remain in existence until the end”, (the processors/processes) “execute different instructions and act on different data”, “the job(work) to be done by each process is allocated dynamically”, that is the processes “self schedule themselves to execute different instructions and act on different data”, thus self assign themselves to cooperate in execution of serial and parallel tasks (as well as replicate tasks) in the program. The notion process was used as a generalization of the term processor in the sense that multiple processes can execute on a processor (to for example exploit larger degrees of parallelism for more efficiency and load balancing). The (IBM) SPMD model was proposed by Darema as an approach different and more efficient than the fork and join that was pursued by all others in the community at that time; it is also more general than just “data parallel” computational model and can encompass fork&join (as a subcategory implementation). The original context of the (IBM) SPMD was the RP3 computer (the 512 prosessor IBM Research Parallel Processor Prototype), which supported general purpose computing, with both distributed and (logically) shared memory. The effectiveness of the (IBM) SPMD was demonstrated for a wide class of applications, the first vendor product in parallel programming; and in MPI (1991 and on), OpenMP (1997 and on), and other environments which have adopted and cite the (IBM) SPMD Computational Model. By the late 1980s, there were many distributed computers with proprietary message passing libraries. The first SPMD standard was PVM. The current de facto standard is MPI. The Cray parallel directives were a direct predecessor of OpenMP.