Оглавление [Скрыть]
Анализ параллельных алгоритмов
-
Анализ параллельных алгоритмов
- Определение вычислительной сложности параллельных алгоритмов
- Сложность анализа из-за взаимодействия нескольких потоков выполнения
- Основная цель – понимание использования ресурсов при изменении количества процессоров
-
Фон и система учета рабочего времени
- Система учета рабочего времени (WT) для описания параллельных алгоритмов
- WT упрощает описание, но позволяет добавлять детали
- Используется в книгах и учебных материалах по параллельным алгоритмам
-
Определения и законы
- Время выполнения Tp включает операции, выполняемые всеми процессорами
- Глубина или диапазон – длина самого длинного критического пути
- Стоимость вычисления – общее время работы всех процессоров
- Трудовое право: стоимость ≥ T1
- Пространственное право: конечное число процессоров не может превзойти бесконечное
-
Показатели эффективности
- Ускорение – прирост скорости при параллельном выполнении
- Эффективность – ускорение работы одного процессора
- Параллелизм – максимальное возможное ускорение на любом количестве процессоров
- Закон размаха ограничивает ускорение при p > T1 / T∞
-
Выполнение на ограниченном числе процессоров
- Закон Брента позволяет “моделировать” неограниченное число процессоров на меньшем количестве
- Ограничения на время вычисления Tp устанавливаются T∞ и T1 вместе