|
|
17.2.99 | 24.2.99 | 3/3/99 | 10/3/99 | 17/3/99 | 24/3/99 | 31/3/99 | 7/4/99 | 14/4/99 | 21/4/99 | 28/499 | 5/5/99 | 12/5/99 | 19/5/99 | 26/5/99 | ||||
| Задорожный Александр Геннадьевич ПММ41
AlexaZ |
Х | Х | X | X | X | X | X | ||||||||||||
| Чернышёв Антон Владимирович ПММ41
Chernshv |
Х | Х | X | X | X | X | X | X | |||||||||||
| Доценко Дмитрий Владимирович ПММ41 | Х | Х | X | X | X | X | X | X | |||||||||||
| Мельникова Анна Владимировна ПММ41 | Х | X | X | X | X | ||||||||||||||
| Цыгулин Алексей ПММ41 | Х | X | X | X | X | X | X | ||||||||||||
| Лектор | |||||||||||||||||||
| Симонов С.А. | Х | Х | X | X | X | X | X | X | |||||||||||
| Кучин Н.В. | X | X | |||||||||||||||||
| задания на дом | 1, 2 | 3, 4 |
Вопросы для экзамена по курсу
"Языки и методы параллельного программирования"
н.с., к.ф.-м.н. С.А. Симонов
Для чего нужно параллельное программирование?
*
Основная терминология: *
процесс, *
разделяемые ресурсы, *
повторно используемые ресурсы, *
потребляемые ресурсы *
критические секции, *
распределенная и общая память, *
средства синхронизации, *
средства передачи данных, *
состояние процессоров, *
тупики (deadlock, livelock), *
детерминированность (однозначность) вычислений *
Проблемы параллельного программирования:
*
корректность *
оценки эффективности параллельных программ *
анализ и отладка параллельных программ *
Классификация
параллельных вычислительных систем по Flynn *
SISD *
MISD *
SIMD (SPMD) *
MIMD *
Общая архитектура классов ВВС, примеры.
Производительность ВС *
ускорение, *
эффективность, *
"Закон Гроша",
"Гипотеза Минского",
Закон Амдала *
Примеры. *
Классификация
вычислительных систем на основе архитектуры соединительных сетей
*
линейка, кольцо, решетка, тор, гиперкуб, дерево, полный граф
*
Возможные
пути развития средств параллельного программирования:
расширение языков, *
расширение библиотек функций *
расширение компиляторов *
уровни языков *
новые языки, компиляторы. *
Уровни параллелизма: *
уровень программ, *
уровень процедур (функций), *
уровень выражений *
уровень команд *
Две предметные задачи:
вычисление значения Pi
комбинаторная задача.
Средства задания параллелизма.
*
Сеть Петри: *
основное определение, свойства сетей Петри: живость, безопасность, ограниченность.
*
Средства синхронизации:
семафоры
Мониторы Brinch Hansen'а
Средства задания параллелизма:
fork... join
parlogin-... parend
неоднозначность
вычислений. *
Тупики; проблемы, связанные с тупиками. *
Балансировка загрузки.
Модель Дейкстры
(охраняемые команды) *
Модель Хоара (CSP) *
конкретные задачи: producer - consumer, amplifier *
Модель
языка с индивидуальными взаимодействиями. Определимость свойств для программ
на этом языке.
Примеры.
Язык Occam: основные конструкции, пример.
*
Модель языка
с групповыми взаимодействиями. Примеры.
Язык Иня.
Основные конструкции.
Язык Actus. Основные конструкции; разделение
данных. Пример: умножение матриц. *
Концепция Linda, примеры.
*
Концепция PVM: конфигурация VM, средства
взаимодействия, средства доступа.
Концепция MPI. *
Сравнение
PVM и MPI: достоинства и недостатки обеих моделей.
Синхронный параллелизм.
История, примеры, общая структура SIMD
систем. *
Языки для SIMD архитектур. Необходимые
средства в языках для SIMD архитектур. *
Язык Parallaxis:
Задание конфигурации ВС;
Задание связей;
Описание данных.
Пересылка данных.
Обмен с host компьютером.
Примеры:
вычисление Pi;
решето Эратосфена
умножение матриц (систолический алгоритм)
Синхронный и асинхронный параллелизм (сравнение), области применения.
Систолические вычисления, волновые вычисления *
VLIW архитектуры. *
Единицы измерения производительности параллельных ВС.
Методы и средства отладки параллельных программ. *
Перспективы параллельных вычислений.
УЧЕБНО-МЕТОДИЧЕСКИЕ МАТЕРИАЛЫ ПО ДИСЦИПЛИНЕ
Курсовые задания
Задания должны быть выполнены в одной из систем PVM/MPI методом простого
перебора, без использования эвристических алгоритмов и оценена (аналитически)
трудоемкость решения задачи. Естественно, при выполнении задач можно пользоваться
свойствами задач, полученных аналитическими средствами из их условий, например,
при решении задачи постоения магического квадрата можно пользоваться тем,
сумма всех чисел по сторокам, столбцам и диагоналям квадрата равна
сумме всех чисел деленной на n.
Путь с запрещенными парами
Заданы ориентированный граф G=(V, A), набор C={(a1,b1),...(an,bn)}
пар вершин из V и две выделенные вершины s, t из V.
Вопрос: Существует ли в G ориентированный путь из s в t, содержащий
не более одной вершины из каждой пары набора C ?
Коммивояжер
Заданы множество C, включающее m городов, расстояние
d(ci,cj) между кождой парой городов ci,
cj из C и положительное число B.
Вопрос: Существует ли маршрут длины не более чем B, проходящий
через все города. Иными словами, существует ли такая перестановка
городов <cp(1), cp(2), cp(m)> , что Sum (i=1 до m-1)
d(cp(i),
cp(i+1)) + d(cp(m), cp(1)) <=B ?
"Магический" квадрат
Задан набор натуральных чисел (a1, a2, ...an2)
Разместить в квадрате со сторой все числа так, чтобы сумма
чисел во всех строках, столбцах и главных диагоналях была одна и та же.
8 ферзей
Найти все возможные размещения 8 ферзей на шахматной доске, при которых
ни один из ферзей не находитсся под боем.
"Подбор пароля"
Задан алфавит {a1, a2, ... an}
и упорядоченная выборка размера m .
Построить алгоритм перебора всевозможных выборок, размера m.