вопросы

Вопросы1. Преимущества и недостатки многопроцессорных систем. Областиприменения многопроцессорных систем.2. Отличия между параллельными и последовательными вычислительнымиархитектурами с точки зрения принципов фон Неймана.3. Виды многопроцессорных систем. Многопроцессорные системы с общейпамятью UMA, NUMA, ccNUMA.Многопроцессорные системы с распределенной памятью, гибридные,векторные.4. Топологии многопроцессорных вычислительных систем.5. Свойства канала передачи данных.

Оценка времени передачи данныхчерез канал. Латентность и пропускная способность.6. Кэш-память и её влияние на эффективность выполнения многопоточныхприложений. Когерентность кэш.7. Внутренний параллелизм, степень параллелизма.8. Ускорение, эффективность, масштабируемость. Закон Амдаля.9. Сверхлинейное ускорение, возможные причины. Формальноепреобразование параллельного алгоритма в последовательный.10. Накладные расходы в параллельных алгоритмах.11. Модель параллельной программы, выполняющейся на вычислительнойсистеме с распределенной памятью.12.

Методы передачи данных (синхронный, асинхронный, …).13. Разделяемые ресурсы. Семафоры Дейкстры, критическая секция,монитор.14. Барьер. Схемы реализации и оценки времени выполнения. Реализациябарьера на основе синхронных обменов. Реализация барьера на основесемафоров Дейкстры.15. Модель параллельной программы, выполняющейся на вычислительнойсистеме с общей памятью. Нити (легковесные процессы, threads).16.

Методы статической и динамической балансировки загрузкипроцессоров.17. Метод сдваивания.18. Метод геометрического параллелизма.19. Метод коллективного решения.20. Метод конвейерного параллелизма.21. Метод диффузной балансировки загрузки.22. Метод серверного параллелизма.23. Отладка параллельных приложений, выполнение которыхсопровождается недетерминированным потоком сообщений.24. Параллельные алгоритмы сортировки данных. Слияние методомсдваивания, двустороннее слияние.

Сети сортировки. Параллельныеалгоритмы сортировки для гибридных вычислительных систем.25. Параллельные алгоритмы генерации псевдослучайных чисел. Требованияк генераторам псевдослучайных чисел. Линейно-конгруэнтныегенераторы. М-последовательности. Достоинства и недостаткигенераторов случайных и псевдослучайных чисел.26. Декомпозиция расчетных сеток. Критерии декомпозиции. Методыдекомпозиции.27. Иерархические алгоритмы разбиения графов. Локальное уточнение.28. Метод спектральной бисекции графов.29. Инкрементный алгоритм декомпозиции графов.30.

Адаптивное интегрирование. Метод локального стека. Методглобального стека.31. Визуализация сеток и сеточных данных.32. Обработка и ввод-вывод больших объёмов сеточных данных,предназначенных для визуализации. Двухуровневое представлениесеточных данных.33. Параллельные алгоритмы многоэкстремальной оптимизации,использующие кривые Пеано.34. Отказоустойчивые алгоритмы для многопроцессорных вычислительныхсистем.

Локальные контрольные точки. Локальное парирование ошибокдля гиперболических систем уравнений.Примеры задач1. Напишете алгоритм для вычислительной системы с распределеннойпамятью, определяющий сумму элементов массива. Считайте, что массивуже распределен между mpi-процессами. Оцените ускорение иэффективность алгоритма в предположении, что время суммированиядвух элементов равно TauC, а время пересылки одного числа междупроцессорами равно TauS.2. Напишете алгоритм для вычислительной системы с общей памятью,определяющий сумму элементов массива.

Оцените ускорение иэффективность алгоритма в предположении, что время суммированиядвух элементов равно TauC, а минимальное время обращения к семафоруравно TauS.3. Нарисуйте сеть четно-нечетного слияния Бетчера для двух упорядоченныхгрупп элементов, содержащих 4 и 7 элементов. Чему равно число тактовработы построенной сети?4. Определить период генератора u[i+1]=( 5*u[i+1]+3) mod 1024.5. Определить значение элемента номер 51 последовательноститрёхразрядных двоичных чисел, формируемых генератором x^i mod (x^4+x^3+ 1).6. Дано: u(t=0;i=0…n)=0, u(t,i=0)=0; u(t=0,…,m;i=n)=1, u(t+1;i=1,...,n-1)=f(u(t,i1),u(t,i),u(t,i+1)).

Напишите параллельную программу для вычислительнойсистемы с распределенной памятью, определяющую значенияu(t=m;i=0,...,n). Приведите оценку ускорения и эффективности программыв предположении, что время однократного вычисления функции f равноTauC, а время пересылки одного числа между процессорами равно TauS.Укажите, какой вид параллелизма Вы использовали.7.

Напишите алгоритм барьера на основе синхронных обменов.8. Напишите алгоритм барьера на основе семафоров Дейкстры..