Содержание
- 2. ОБЩАЯ СХЕМА РАЗРАБОТКИ Общая схема разработки параллельных алгоритмов
- 3. Итеративный процесс (1) Осуществление декомпозиции Разделение задачи на части (подзадачи), которые могут быть реализованы в значительной
- 4. Итеративный процесс (2) Этапы не обязательно выполняются в порядке следования Отдельные этапы могут повторяться несколько раз
- 5. Общие рекомендации Равномерное распределение нагрузки по процессорам Минимизация информационных связей между подзадачами
- 6. КОММУНИКАЦИОННАЯ ТРУДОЕМКОСТЬ Анализ коммуникационной трудоемкости
- 7. Анализ алгоритма На уровне отдельных подзадач Граф операций подзадачи Граф объектов памяти подзадачи На уровне всего
- 8. Граф информационных связей Подзадачи Вершины графа Каналы передачи данных Ребра графа
- 9. Подзадача Подзадача (процесс или поток) Выполняемая на процессоре программа, которая реализует определенную подзадачу, использует для своей
- 10. Канал передачи данных Канал передачи данных Логический или физический канал передачи данных, представленный в виде очереди
- 11. Анализ коммуникаций Множество факторов Синхронная/асинхронная передача данных Синхронное/асинхронное получение данных Пакетный/потоковый режим передачи данных И т.п.
- 12. РАЗДЕЛЕНИЕ НА НЕЗАВИСИМЫЕ ЧАСТИ Разделение вычислений на независимые части
- 13. Основные критерии разделения Выбрать подходящий уровень декомпозиции задачи Разумное сочетание между количеством подзадач и ясностью схемы
- 14. Виды параллелизма Параллелизм по данным Однотипная обработка большого объема данных (наиболее частая ситуация) Определяется оптимальное распределение
- 15. Оценка качества этапа Не увеличивает ли выполненная декомпозиция объем вычислений и необходимый объем памяти? Возможна ли
- 16. ВЫДЕЛЕНИЕ ИНФОРМАЦИОННЫХ СВЯЗЕЙ Выделение информационных связей между подзадачами
- 17. Сложность декомпозиции С одной стороны Самый простой подход – выделить базовые подзадачи и определить информационные связи
- 18. Способы передачи данных Локальные/глобальные Структурные/произвольные Статические/динамические Синхронные/асинхронные
- 19. Оценка качества этапа Соответствует ли вычислительная сложность подзадач интенсивности их информационных взаимодействий? Является ли одинаковой интенсивность
- 20. МАСШТАБИРОВАНИЕ ВЫЧИСЛЕНИЙ
- 21. Возможность масштабирования Если количество подзадач отличается от числа процессоров Подзадачи должны иметь примерно одинаковую вычислительную сложность
- 22. Оценка качества этапа Не ухудшится ли локальность вычислений после масштабирования имеющегося набора подзадач? Имеют ли подзадачи
- 23. РАСПРЕДЕЛЕНИЕ ПОДЗАДАЧ ПО ПРОЦЕССОРАМ
- 24. Способы распределения Статически Автоматически
- 25. Оценка качества этапа Не приводит ли распределение нескольких задач на один процессор к росту дополнительных вычислительных
- 27. Скачать презентацию