В інформатиці паралелізм — це властивість систем, при якій кілька обчислень виконуються одночасно, і при цьому, можливо, взаємодіють один з одним. Обчислення можуть виконуватися на декількох ядрах одного чіпа витісняють з поділом часу потоків на одному процесорі, або виконуватися на фізично окремих процесорах. Для виконання паралельних обчислень розроблено ряд математичних моделей, у тому числі мережі Петрі, обчислення процесів, моделі паралельних випадкових доступів до обчислень і моделі акторів.
Слід зазначити, що в англомовній літературі для опису поняття паралелізму в комп'ютерних науках використовуються два терміни: Concurrency (одночасність) і Parallelism (паралелізм). Між ними є деяка відмінність, про що буде сказано нижче. У російськомовній літературі для обох цих термінів використовується тільки один переклад: паралелізм, що створює певні термінологічні труднощі.
Оскільки обчислення в паралельних системах взаємодіють один з одним, число можливих шляхів виконання може бути надзвичайно велика, і результуючий підсумок може стати недетерминированным. Паралельне використання загальних ресурсів може стати одним з джерел недетерминированности, що призводить до таких проблем, як взаємне блокування або фатальний недолік ресурсів.[]
Побудова паралельних систем вимагає пошуку надійних методів координації виконуваних процесів, обміну, розподілу пам'яті і планування для мінімізації часу відгуку і збільшення пропускної здатності.
Теорія паралельних обчислень є активною областю досліджень теоретичної інформатики. Одним з перших пропозицій в цьому напрямку була плідна робота Карла Адама Петрі мереж Петрі на початку 1960-х. У наступні роки був розроблений широкий спектр формалізмів для моделювання і опису паралельних систем.
Зараз розроблено велике число формальних методів для моделювання та розуміння роботи паралельних систем, в тому числі:[2] Паралельний випадковий доступ до комп'ютера[3] Модель акторів Обчислювальні пов'язані моделі, наприклад, модель масового синхронного паралелізму Мережі Петрі Обчислення процесів Простір кортежів, наприклад, Linda SCOOP (Simple Concurrent Object-Oriented Programming — Просте паралельне об'єктно-орієнтоване програмування)
Деякі з цих моделей паралелізму призначені в першу чергу для логічних умовиводів і опису специфікацій, тоді як інші можуть бути використані протягом всього циклу розробки, включаючи проектування, впровадження, доказ істинності результатів, тестування і моделювання паралельних систем.
Поширення різних моделей паралелізму спонукало деяких дослідників розробити способи об'єднання цих теоретичних моделей. Наприклад, Чи і Санджованни-Винсентелли показали, що так звану модель «мічених сигналів можна використовувати для створення загальної основи для опису денотаційної семантики різних моделей паралелізму,[] а Нільсен, Сассун і Винскль показали, що теорія категорій може бути використана для забезпечення єдиного розуміння різних моделей.[]
Теорема подання паралелізму з моделі актора забезпечує досить загальний спосіб опису паралельних систем, замкнутих в тому сенсі, що вони не отримують повідомлень ззовні. Інші методи опису паралелізму, як, наприклад, обчислення процесів, можуть бути описані через модель актора, використовуючи двофазний протокол фіксації.[] Математичні позначення, які використовуються для опису замкнутої системи S, забезпечують більшою мірою хороше наближення, якщо вони будуються на основі початкового поведінки, позначуваного ⊥S, з використанням апроксимуючої функції поведінки прогресії.[] Тоді для позначення S будуються наступним чином:
DenoteS ≡ ⊔i∈ω progressionSi(⊥S)
Таким чином, S може бути виражена математично за допомогою всіх його можливих поводжень.
Щоб забезпечити логічні міркування про паралельних системах, можна використовувати різні види темпоральних логік[]. Деякі з них, як, наприклад, лінійна темпоральна або логіка обчислювального дерева, дозволяють робити твердження про послідовності станів, через які паралельна система може пройти. Інші ж, такі як логіка дій обчислювального дерева, логіка Хеннессі-Мілнера або темпоральна логіка дій Лэмпорта, будують свої твердження від послідовності дій (зміни станів). Основне застосування цих логік полягає в запису специфікацій для паралельних систем
У цьому розділі буде використовуватися два поняття паралельності, властиві англомовній літературі, оскільки мова піде про порівняння їх один з одним. Термін Concurrency буде переводитися «одночасність», а термін Parallelism буде переводитися «паралелізм».
Одночасне програмування включає в себе мови програмування та алгоритми, що використовуються для реалізації одночасних систем. Одночасне програмування зазвичай вважається більш загальним поняттям, ніж паралельне програмування, оскільки воно може містити довільні динамічні моделі спілкування і взаємодії, тоді як паралельні системи найчастіше реалізують визначені заздалегідь і добре структуровані моделі зв'язків. Основними цілями одночасного програмування є коректність, ефективність, стійкість. Одночасні системи, такі як операційні системи та системи управління базами даних призначені насамперед для роботи в невизначених умовах, у тому числі з урахуванням автоматичного відновлення після збою, вони не повинні несподівано припиняти роботу. Деякі одночасні системи здійснюють роботу у вигляді прозорої одночасності, при якій одночасні обчислювальні сутності можуть конкурувати за використання одного і того ж ресурсу, але суть цієї конкуренції прихована для програміста.
Оскільки одночасні системи використовують загальні ресурси, вони зазвичай вимагають наявність будь-якого арбітра, вбудованого в їх реалізацію (часто в базове обладнання) для управління доступом до цих ресурсів. Використання арбітрів створює ймовірність невизначеності в одночасних обчисленнях, яка має велике значення для практики, в тому числі для забезпечення коректності та ефективності. Наприклад, арбітраж не виключає необмежений індетермінізм, який пов'язаний з проблемою перевірки моделей, що є причиною вибухового характеру простору станів і може навіть стати причиною утворення моделі з нескінченним числом станів.
Деякі одночасні моделі програмування включають створення сопроцессов і детермінованою одночасності. У цих моделях потоки виконання по управлінню процесами явно віддають своє кванти часу небудь системі, або іншого процесу.
