Differences

This shows you the differences between two versions of the page.

--- courses:high_performance_computing:questions [2016/10/31 01:21] – created kel
+++ courses:high_performance_computing:questions [2016/11/24 00:07] (current) – kel
@@ Line 1: / Line 1: @@
 ====== Вопросы к проверке знаний ======
+===== 1. Уровни абстракции технологий =====
+Расположите в порядке увеличения степени абстракции технологии высокопроизводительных вычислений:
+  - OS Threads, SSE/MMX, C++11 Threads/Java Threads, TBB/Fork-Join framework
+  - SSE/MMX, OS Threads, TBB/Fork-Join framework, C++11 Threads/Java Threads
+  - SSE/MMX, OS Threads, C++11 Threads/Java Threads, TBB/Fork-Join framework
+  - OS Threads, TBB/Fork-Join framework, C++11 Threads/Java Threads, SSE/MMX
+===== 2. Закон Амдала =====
+Что показывает закон Амдала:
+  - Прирост производительности в зависимости от доли последовательного кода и числа вычислительных элементов
+  - Прирост производительности в зависимости от числа вычислительных элементов и используемой технологии распараллеливания
+  - Число вычислительных элементов, необходимое для достижения заданного уровня роста производительности
+  - Долю последовательного кода, производительность которого невозможно повысить
+===== 3. Завершение потоков =====
+Как называются функции, внутри которых, в зависимости от используемой технологии, происходит проверка на необходимость завершения работы потока и по результатам проверки возможно выкидывание исключений или завершение потока с применением стека зарегистрированных функций:
+  - Функции завершения потока
+  - join-функции
+  - Cancellation / interruption points
+  - Signal handlers
+===== 4. Spin mutex =====
+Чем отличается spin mutex от обычного mutex:
+  - Остаётся всегда в user space
+  - Остаётся всегда в kernel space
+  - Ничем не отличается
+  - Позволяет читателям производить операции параллельно
+===== 5. Wait/notify =====
+В каком состоянии находится примитив синхронизации (mutex) в приведённом коде на 1, 3 и 4 строках:
+<code c++>
+: boost::unique_lock<boost::mutex> lock(mutex);
+:
+: while (messageQueue.empty())
+:   conditionVariable.wait(lock);
+:
+</code>
+  - Во всех строках захвачен
+  - Во всех строках освобождён
+  - Захвачен в 1 и 4 строках, в 3 на время вызова //wait// освобождается
+  - Захвачен в 1 строке, в 3 и 4 освобождён
+===== 6. Ранжирование алгоритмов =====
+Расположите алгоритмы синхронизации в порядке увеличения потенциальной производительности в жёсткой конкурентной среде:
+  - Грубая, тонкая, оптимистичная, неблокирующая
+  - Тонкая, грубая, оптимистичная, неблокирующая
+  - Неблокирующая, оптимистичная, грубая, тонкая
+  - Грубая, тонкая, неблокирующая, оптимистичная
+===== 7. Выбор алгоритма =====
+Отметьте вид алгоритмов синхронизации, обычно реализуемый на CAS-операциях и позволяющий добиться максимальной независимости исполнения потоков, гарантируя общий прогресс системы:
+  - Грубая
+  - Тонкая
+  - Оптимистичная
+  - Неблокирующая
+===== 8. Wait-free алгоритм =====
+Выберите корректное определение wait-free класса алгоритмов:
+  - Любой поток ожидает, пока хотя бы один другой поток не выполнил свою операцию
+  - Любой поток может выполнить свои функции за конечное число шагов, если ни один другой поток не находится в критической секции
+  - Система в целом продвигается вперед не зависимо ни от чего
+  - Любой поток может выполнить свои функции за конечное число шагов, не зависимо ни от чего
+===== 9. Определение типа ошибки =====
+Какая ошибка потенциально может возникнуть в приведённом коде:
+<code c++>
+void f() {
+  first_mutex.lock();
+  second_mutex.lock();
+  ...
+}
+void g() {
+  second_mutex.lock();
+  first_mutex.lock();
+  ...
+}
+</code>
+  - Гонка данных (Data Race)
+  - Взаимная блокировка (Deadlock)
+  - Проблема ABA
+  - Инверсия приоритетов
+===== 10. Реализация lock-free алгоритмов =====
+Почему lock-free алгоритмы легче реализовать на языке со сборщиком мусора, нежели на нативных языках, например C++:
+  - Невозможна инверсия приоритетов
+  - Наличие существующих базовых контейнеров в java.util.concurrent
+  - Невозможна проблема ABA
+  - Наличие CAS-операций
+===== 11. Профилирование =====
+Укажите какие виды профилирования желательно применить для комплексного анализа проблем приложения:
+  - Инструментирующее и сэмплирующее
+  - Поиск hot spots и анализ издержек на ожидание и синхронизацию (locks and waits)
+  - Интрузивное и неинтрузивное
+  - В отладочной сборке и release-сборке
+===== 12. Выбор шаблона =====
+Укажите, какой шаблон проектирования позволяет повторно использовать один и тот же вычислительный поток для решения нескольких задач и минимизировать время на создание новых потоков:
+  - Thread Pool
+  - Double Check
+  - Local Serializer
+  - Pipeline
+===== 13. Выбор шаблона =====
+Укажите, какой шаблон проектирования позволяет эффективно организовать потоковую обработку данных:
+  - Thread Pool
+  - Double Check
+  - Recursive Data
+  - Pipeline
+===== 14. Узкое место при работе с контейнерами =====
+В чём заключается одна из основных причин просадки производительности (увеличение времени выполнения операции) при активной конкурентной работе с контейнерами (в предположении, что процессорных ресурсов достаточно):
+  - Сложность поиска / удаления / вставки элементов
+  - Переключение контекста процесса
+  - Потокобезопасность функции new
+  - Промашки по кэшу процессора
+===== 15. Task-based разработка =====
+Выберите технологию, предоставляющую инструменты работы в терминах задач, скрывая вычислительные потоки внутри:
+  - OpenMP
+  - MPI
+  - Intel TBB / ForkJoin framework
+  - Java Threads
+===== 16. Выбор технологии =====
+Выберите технологию, для которой характерна адресация в терминах групп и коммуникаторов, с возможностью создания виртуальных топологий:
+  - OpenMP
+  - MPI
+  - Intel TBB / ForkJoin framework
+  - Java Threads
+===== 17. Оптимизации в компиляторе =====
+Выберите оптимизацию JIT-компилятора, которая позволяет уменьшить время, затрачиваемое на захват и освобождение примитива синхрониации, не переходя в некоторых случаях в kernel space:
+  - Объединение захвата примитивов
+  - Оптимистичный захват
+  - Адаптивные блокировки
+  - Замена виртуального вызова
+===== 18. Модель памяти =====
+Выберите модель памяти, которая гарантирует acquire/release семантику доступа к памяти:
+  - Sequential Consistency
+  - Strong-ordered
+  - Weak-ordered
+  - Super-weak
+===== 19. Асинхронный ввод/вывод =====
+Выберите тип ввода/вывода, наиболее подходящий для реализации высоко нагруженных серверных частей системы:
+  - Синхронный блокирующий
+  - Асинхронный блокирующий
+  - Синхронный неблокирующий
+  - Асинхронный неблокирующий
+===== 20. Консенсус =====
+Какое консенснусное число CAS-операций:
+  - 1
+  - 2
+  - 2N-2 (где N-число ячеек памяти, доступных для CAS)
+  - Бесконечность