(Отново) За паралелното програмиране

Вместо увод

По-добре късно, отколкото още по-късно. Доста вода изтече и много неща се промениха, откакто за последно писах тук за HPC. Всъщност откакто за последно писах тук изобщо. Едно от непроменимите неща, обаче, остава тенденцията на прехода от монолитни процесори с едно свръх-бързо ядро към процесори с множество относително по-бавни ядра или такива с огромен брой много прости ядра (напр. GPU). Дори часовниците не остават незасегнати. Силен двигател на тази тенденция е и масовото навлизане на машинното самообучение.¹

За разлика от процедурното и обектно-ориентирано програмиране, които, въпреки множествата нива на насложена абстракция, в крайна сметка запазват класическата фон Нойман парадигма на последователен набор от инструкции, опериращи върху някакъв модел на данни в паметта, програмирането на паралелните и разпределени системи изисква качествено нов начин на мислене. Класически проблеми като как най-бързо или с най-малко количество работна памет да бъде изпълнен даден алгоритъм, се допълват с често неортогонални проблеми като как да бъде декомпозиран модела така, че комуникацията и синхронизацията между отделните процесорни единици да бъде сведена до минимум. Освен това, на преден план стои и въпросът за методите на изразяване на необходимия паралелизъм. И доколкото декомпозирането на проблемите е изключително тежка задача, граничеща с изкуство, то програмното изразяване на паралелизма е значително по-проста (но в никакъв случай проста) такава, както ще се опитам да покажа в тази и последващите статии по въпроса, като ще се фокусирам върху няколко парадигми, придобили статута на де факто стандарти.

Паралелни архитектури

Не може да се говори за практическо паралелно програмиране, без това да става в контекста на хардуера, върху който ще се изпълняват крайните програми. Съществуват, най-общо казано, два ортогонални класа паралелни архитектури.

Първият клас е този на системите със споделена памет, при които множество изчислителни елементи (ИЕ) имат едновременен достъп до общ блок памет, като блокът може да бъде или относително монолитен и да осигурява еднакво бърз достъп от всеки един ИЕ, известно като униформен достъп до паметта UMA (Uniform Memory Access), или на йерархични нива, при които някои области от паметта са по-близо до определени ИЕ и съответно осигуряват по-ниско време на достъп и по-висока пропускателна способност от други, по-далечни области, известно като неуниформен достъп до паметта NUMA (от Non-Uniform Memory Access). Класически пример за UMA от света на x86 са многопроцесорните системи с Front-Side Bus технология за връзка между процесорите и контролера на основната памет, т.е. всичко от времето преди AMD64 и Intel Nehalem, докато пример за NUMA са всички многопроцесорни системи, където всеки процесор има собствен контролер на паметта, което включва практически всяка съвременна многопроцесорна система.

Вторият клас е този на системите с разпределена памет, при които множество ИЕ, всеки със собствен блок памет, са свързани с някакъв транспортен механизъм за обмяна на информация. Всеки ИЕ има директен достъп единствено до своя блок памет и при нужда обменя информация с останалите ИЕ под формата на съобщения, предавани по транспортния механизъм, който най-често е високоскоростна мрежа с ниско времезакъснение.

Разделението между двата класа е предимно на ниво физическа реализация, тъй като на логическо ниво всеки един от тях прави възможно емулирането на другия. Например, процесите в съвременните операционни системи (ОС) оперират в собствено виртуално адресно пространство и обменят информация помежду си само чрез специални комуникационни механизми на ОС, въпреки че съществуват в рамките на един и същ блок физическа памет. И обратно, механизмът на виртуалната памет прави възможно автоматичното споделяне и мигриране на данни между физически отделни блокове памет, известно като (виртуална) разпределена споделена памет или (v)DSM (от (virtual) Distributed Shared Memory). Струва си да се отбележи, че дори многопроцесорните системи в наши дни са пример за хардуерна реализация на разпределена споделена памет, тъй като всеки един процесор автоматично препраща операциите за достъп до области памет, намиращи се извън собственото му физическо адресно пространство, към съответния процесор, където те се намират.

Бидейки ортогонални, двата класа могат да се комбинират, като това е по-скоро норма, отколкото изключение. Например, практически всеки изчислителен клъстер в наши дни се състои от множество дву- или четирипроцесорни изчислителни възли, свързани помежду си с високоскоростна мрежа с ниско закъснение. Всеки изчислителен възел е NUMA на глобално системно ниво, докато ядрата във всеки един процесор имат UMA достъп до споделения кеш от последно ниво и до блока памет на него процесор.

Важна характеристика на една паралелна архитектура е нейната възможност да се разраства като брой ИЕ или т.нар. мащабируемост. UMA е изключително ограничена в това отношение, главно поради експоненциалното нарастване на хардуерната сложност с броя на ИЕ, които имат достъп до паметта. NUMA на теория позволява неограничено йерархично разрастване, но на практика е ограничена от изискването за кешова кохерентност. По-голямата част от NUMA реализациите са кеш-кохерентни, т.нар. ccNUMA, което означава, че промените в локалния кеш на един ИЕ се разпространяват и автоматично отразяват в кешовете на другите ИЕ. Без подобен механизъм реализацията на NUMA би била много по-проста, но това би било за сметка на значително усложнен програмен модел. Системите с разпределена памет са принципно неограничени, тъй като обмяната на съобщения там е явна и може да се локализира в определени области, когато алгоритъмът е избран подходящо.

SIMD и VLIW

Предните два класа се отнасят за паралелни системи, състоящи се от множество ИЕ, като всеки ИЕ е малко или много завършено процесорно ядро с контролна логика, АЛУ, изпълнителни блокове, конвейри и прочие. Но паралелизмът може да е на много по-ниско (или по-фино) ниво, по-специално на ниво инструкция, като това е бил пътят за постигане на изключително висока производителност през 70-те години на миналия век. Практичният паралелизм на ниво инструкция бива най-общо два вида.

Първият вид е SIMD (Single Instruction Multiple Data), при който една инструкция действа едновременно върху вектор (няколко еднотипни единици) от данни. Дължината на вектора в различните архитектури варира от два до стотици елемента. Дългите веркторни операции са начинът, по който Cray-1 постига през 1975 г. космическата за тогава производителност от над 100 MFLOPS². Основен недостатък на подобни системи е тяхната тясна специализираност в обработка на големи масиви от еднотипни данни. Далеч по практични са късите векторни операции, с каквито е снабден практически всеки съвременен процесор, независимо от архитектурата му.

Вторият и значително по-рядко срещан вид е VLIW (Very Long Instruction Word), при който една инструцкия кодира множество различни операции, които се изпълняват едновременно от различни независими изпълнителни блокове в процесора. За разлика от SIMD, който е вид паралелизъм по данни, VLIW е паралелизъм по задачи (или операции). Типичен пример са повечето цифрови сигнали процесори (DSP) и по-ранните модели GPGPU на ATI. Вид VLIW е и EPIC архитектурата на Itanium.

Следва да се отбележи, че векторизацията обикновено е единственият начин за пълно използване на изчислителните възможности на съвременните процесорни ядра.

Програмни модели

Всеки един от двата класа паралелни архитектури може да бъде разглеждан по много различни начини на програмно ниво, като обаче някои от тези начини са по-подходящи и естествени за съответния клас, а други – не толкова. Наличието на споделена памет позволява лесна обмяна на информация между отделните ИЕ под формата на споделени променливи. И не само това – архитектурата позволява споделяне и на изпълнимите инструкции, което силно опростява модела на зареждане и изпълнение на паралелните програми. Най-удобното в случая е, че съществува готов и широкоразпространен програмен модел, който съответства директно на архитектурата – този на многонишковите процеси, където нишката е абстракция на независимо изпълняващ се поток инструкции. Нишките могат да бъдат както отделни контексти в рамките на един последователен поток, между които се превключва с някакъв механизъм в потребителски режим, често наричани зелени нишки (green threads по името на първата Java библиотека за многонишково изпълнение) или фибри (fibers), така и олекотени процеси (или LWP от Light-Weight Processes), които споделят в рамките на един процес на ОС общо адресно пространство и системни обекти като дескриптори на отворени файлове и мрежови съединения, но се изпълняват независимо един от друг. Съществуват множество приложни програмни интерфейси (API) за създаване, контрол и синхронизация на двата вида нишки, като LWP са значително по-полезни в контекста на паралелното програмиране, тъй като могат да се изпълняват върху различни ИЕ.

Писането на многонишкови програми е като цяло трудоемко и най-вече силно платформенозависимо, поради което са разработени различни абстрактни модели, които да го облекчат. Един такъв модел е OpenMP, който ще бъде предмет на следващата статия от серията. OpenMP използва специални директиви на компилатора, реализирани под формата на прагми (C/C++) или коментари (Fortran), които модифицират поведението на съществуващите езикови конструкции. Това позволява не само създаването на нов паралелен софтуер, но и прагматичната постъпкова паралелизация на съществуващ последователен код. Версия 4.0 на OpenMP спецификацията добави и преносими SIMD конструкции, които да заместят различните за всеки един компилатор директиви за векторизация на кода.

Малко по-различен модел е този на Intel Threading Building Blocks (Intel TBB или просто TBB), което е библиотека от контейнерни класове и алгоритми за C++. За разлика от OpenMP, TBB не изисква специален компилатор и се поддържа на практически всяка платформа, за която съществува достатъчно съвременна реализация на C++.

Към класа на многонишковото програмиране спадат и платформите за изпълнение на операции с общо предназначение върху графичен хардуер (GPGPU от General-Purpose computing on Graphics Processing Units) като CUDA и OpenCL. OpenCL е интересен с това, че е отворен стандарт и поддържа не само различен вид графичен хардуер, но също така всякакъв вид хетерогенни изчислителни добавки, известни като ускорители (accelerators), включително и стандартни процесори и FPGA. Както CUDA, така и OpenCL, са платформи от сравнително ниско ниво, които оставят видими значително количество хардуерни детайли, поради което върху тях съществуват редица абстракции от по-високо ниво. Една такава е SYCL, продукт на организацията зад OpenCL, която е набор от класове и алгоритми на C++ и среда за изпълнение, която динамично превежда класовете и алгоритмите в OpenCL код. Друга абстракция и надстройка на SYCL е Data-Parallel C++ (или DPC++) – отроче на Intel, което те искрено се надяват да се наложи като новият отворен стандарт. Дали това ще се случи наистина, единствено времето ще покаже. SYCL и DPC++ са много по-близки до TBB като структура на програмите, отколкото до OpenMP.

Един интересен, макар и все още не особено широко приет похват за многонишково програмиране, е този на функционалните езици. Комбинацията от мързеливи функционални трансформации върху непроменими стойности и липсата на скрито вътрешно състояние (поне в чистите функционални езици) правят функционалното програмиране особено приемливо, не само заради относително естественото изразяване на най-различни паралелни операции, но и поради автоматичното елиминиране на много от проблемите, които възникват при поставяне на класическите императивни идеи в многонишков контекст, за които проблеми ще стане дума в последващите статии.

Програмирането на архитектури със споделена памет е значително по-сложно, тъй като липсата на споделено адресно пространство води до необходимост от явен обмен на споделена информация между отделните ИЕ. Това най-често става под формата на съобщения, които представляват пакети от силно-, слабо- или напълно нетипизирана информация. Самото предаване може да бъде както функционалност на операционната система, така и функционалност на някакъв вид междинен софтуерен слой и/или среда за изпълнение (middleware). Като пример за първата може да се посочи приложният интерфейс на BSD сокетите, който направи възможно широкото приемане на TCP/IP и експлозията на мрежовите услугите и Internet. И както сокетите са де факто стандартният интерфейс за обмяна на неструктурирана информация върху множество различни мрежови протоколи в слабо свързани системи, така интерфейсът за предаване на съобщения MPI (Message Passing Interface) е де факто стандартът за предаване на структурирани съобщения в силно свързани системи, каквито са повечето изчислителни архитектури с разпределена памет. MPI стъпва върху множеството съществуващи транспортни механизми и скрива редица техни детайли, като предоставя на приложенията сравнително прост метод за адресация на съобщенията, както и готова реализация на някои често срещани и относително примитивни операции.

Практически примери

Идеята ми е да покажа в рамките на няколко последователни статии най-разпространените парадигми за паралелно програмиране, като във всяка една от тях да покажа на практика процесите на декомпозиция и реализация с използването на съответната парадигма. За целта ми трябват примери, които хем да бъдат достатъчно прости, за да не се загуби паралелизацията в шума на основния код, хем да имат някакво практическо значение. Затова и се спрях на следните три:

• k-means клъстеризация – широкоизползван и достатъчно прост за реализация метод от машинното самообучение;
• игра Живот на Конуей – любим пример за клетъчен автомат, също така почит към паметта на автора му, Джон Конуей, който наскоро стана нелепа жертва на COVID-19;
• оцветяване на множеството на Манделброт – солидна основа за дискусия на особеностите при разпределяне на работата в паралелните системи, страничен продукт на чието решение са красиви визуализации на де факто символа на фракталната математика.

Както обясних по-рано, OpenMP представлява набор от директиви на компилатора, които позволяват постъпковата паралелизация на съществуващи последователни програми, поради което и ще започна серията именно с него, като едновременно с това ще представя всеки един от трите примера и тяхното класическо (последователно) решение. Като език ще използвам C++, защото той е най-големият общ делител на всички методи, които искам да разгледам, като ще се придържам към максимално C-подобно подмножество, т.е. нищо няма да бъде идиоматичен C++. За MPI ще дам и пример на Python, тъй като неофициалната реализация mpi4py продължава да набира популярност. Всички примери ще бъдат по възможност междуплатформени, с изключение на тези за “ръчното” многонишково програмиране, а където е възможно ще приведа и времето за изпълнение в различни конфигурации върху Intel i7-5820K под 64-битов Windows 10.