Конспект курса «Параллельные и распределенные вычисления»

Конспект «Параллельные и распределенные вычисления»

Синхронизация обеспечивает:

• безопасный доступ к общим данным
• координации действий между потоками

Как избежать взаимной блокировки (deadlock):

• не захватывать более одной блокировки одновременно
• всегда захватывать блокировки в одном порядке (упорядочить объекты блокировки каким-либо образом)
• добровольно освобождать захваченную блокировку (lock/tryLock)

Гарантированная остановка потока

public class StopThread3 {

    private static volatile boolean stopRequested;

    public static void main(String[] args) throws InterruptedException {
        Thread backgroundThread = new Thread(new Runnable() {
                public void run() {
                    int i = 0;
                    while (!stopRequested)
                        i++;
                }
            }
        );
        backgroundThread.start();
        TimeUnit.SECONDS.sleep(1);
        stopRequested = true;
    }
}

• Проверка флага volatile внутри run()
• Thread.interrupt()
  • для заблокированных потоков выбрасывает InterruptedException
    • работает для sleep(), join(), wait()
    • не работает для I/O, synchronized
  • для не заблокированных потоков проверка Thread.interrupted()

Классификация вычислительных систем (Flynn)

Детализация MIMD:

• Системы с общей разделяемой памятью (мультипроцессоры)
• Системы с распределённой памятью (мультикомпьютеры)
• Гибридные системы

False sharing — хранение данных в кэше в виде линий:

• False sharing в многопоточном приложении на Java
• Делиться не всегда полезно: оптимизируем работу с кэш-памятью

Закон Амдала иллюстрирует ограничение роста производительности вычислительной системы с увеличением количества вычислителей:

Закон Густавсона — Барсиса — оценка максимально достижимого ускорения выполнения параллельной программы, в зависимости от количества одновременно выполняемых потоков вычислений («процессоров») и доли последовательных расчётов:

• Foster, Designing and Building Parallel Programs
• Mattson T., Sanders B., Patterns for Parallel Programming

Декомпозиция бывает: по заданиям, по данным, по потокам данных.

Декомпозиция по заданиям делится на task parallelism (линейная процедура) и divide and conquer (рекурсивная процедура).
Декомпозиция по данным делится на геометрическую декомпозиция (линейная процедура) и рекурсивные данные (рекурсивная процедура).
Декомпозиция по потокам данных делится на конвейерную обработку (регулярный) и координацию на основе событий (нерегулярная).