Практикум на ЭВМ

171 (2017-2018) группа

Максим Журавлев

Студент TODO №1 №2 №3 №4
219 1 2 3 1 2 3 4 1 2 3 4 5 6 1 2 3 4
Богданов Егор 17
Евгений Богданов 15
Завадский Илья 16
Келим Илья 17
Кутленков Дмитрий 14
Мясников Владислав 14
Орачев Егор 17
Осипова Александра 14
Погребной Дмитрий 17
Погребной Дмитрий 14
Рыбина Екатерина 17
Сергеев Егор 15
Фунт Дина 17
Ярош Дмитрий 15

Задачи

Домашняя работа 5. 22.10.18
[Дополнительно] Atomic vs. Non-Atomic Operations
[Дополнительно] Memory Ordering at Compile Time
[Доплонительно] Memory Barriers Are Like Source Control Operations
[Дополнительно] Weak vs. Strong Memory Models
[Дополнительно] Acquire and Release Semantics
Домашняя работа 4. 11.10.18
[Дополнительно] Обзор параллельных коллекций Scala
[Дополнительно] Шипилёв о недавно разработанном параллельном сборщике мусора Shenandoah. Часть 1.
[Дополнительно] Шипилёв о недавно разработанном параллельном сборщике мусора Shenandoah. Часть 2.
Шипилёв — Прагматика Java Memory Model
Шипилёв — Близкие Контакты JMM-степени
[Дополнительно] Андрей Паньгин — Искусство Java профилирования
[Дополнительно] Цикл статей автора C++ библиотеки c набором lock-free структур данных
[К заданию] WampServer
Определения blocking -> lock-free -> wait-free на одной странице с примерами
JMM Pragmatics слайды
  1. Реализовать mini web crawler. На вход программа получает URL сайта, не являющегося SPA, и максимальную глубину.
    Примерный алгоритм:
    - взять путь к очередной странице из некоей очереди,
    - скачать страницу,
    - найти все ссылки, добавить их в очередь на скачивание (одна страница не должна быть скачана более одного раза) ,
    - поставить страницу в очередь для сохранения на диск.
    В первой версии использовать пул потоков и коллекцию(и) из java.util.concurent

  2. Заменить используемые многопоточные коллекции на собственную реализацию. Реализация должна быть сложнее, чем "грубый" лок (synchronized(this) в каждом методе).

  3. Заменить стандартный пул потоков своей реализацией.

  4. Провести замеры производительности. Зависимость от кол-ва потоков, стандартных/собственных коллекций.
    Чтобы исключить влияние сетевых задержек, эксперименты лучше проводить используя web server, запущенный на локальной машине. Директория с файлами сайта на одном физическом диске, место сохранения скачанного на другом.

Домашняя работа 3. 05.10.18
[Дополнительно] Who ordered memory fences on an x86? - Пример алгоритма требующего барьеров памяти для корректной работы
[Дополнительно] Презентация про виды гарантий, примеры сломанных алгоритмов и алгоритмы когерентности кешей
[Лополнительно] Выжимка статьи, дающей формальное описание модели памяти x86, для инженеров
[К заданию]Introduction to parallel & distributed algorithms
[Дополнительно] What every programmer should know about computer memory
  1. Ознакомиться со статьей [К заданию]

  2. Реализовать алгоритм 3.3 (+ однопоточная версия)

  3. Упражнение 8. Найти решение. Реализовать (+ однопоточная версия).

  4. Упражнение 9. Найти решение. Реализовать (+ однопоточная версия).

  5. Упражнение 10. Найти решение. Реализовать (+ однопоточная версия).

  6. Произвести измерения времени работы
    - однопоточных версий,
    - многопоточных (n = 1, 2, 4, 8, ... количество ядер * 2)

Домашняя работа 2. 27.09.18
[К заданию]Введение в JMH на русском
[К заданию]Документация по JMH
[Дополнительно/К заданию]Презентация Шипилева о микробенчмаркинге в Java
[Дополнительно]Советы по использованию JMH
[Дополнительно]Анимированные пояснения к java.util.concurent.*
[Дополнительно]Обзор java.util.concurrent.* (Java 7)
  1. Реализовать Blur фильтр в соответствие с описанием, которое будет дано в классе.

  2. Применить фильтр к изображению, используя несколько потоков параллельно, разбивая пиксели на горизонтальные и вертикальные полосы.

  3. Проанализировать влияние на ускорение количества потоков, направления разбиения и размера картинки. Для замеров использовать JMH или другой бенчмарк-фреймворк.

  4. Массив байт для обработки формировать чтением картинки из файла.
    Обработанную фильтром картинку созранять файл.
    Время чтения - записи в замерах участвовать не должно.

Домашняя работа 1. 20.09.18
[К заданию]Отладка как процесс
[Дополительно]24-ядерный CPU, а я не могу набрать электронное письмо
[Дополительно]Рефакторинг программы на Go: ускорение в 23 раза
[К заданию]Guide to Java locks
[К заданию]Meaning of “ StringBuilders are not thread safe”
[К заданию]Документация Thread
Слайды к книге
Роман Елизаров. Слайды к выступлению на Devexperts 2016, на русском. Пересекаются с первыми лекциями.
  1. В статье "Отладка как процес" найти описание бага, который не возник бы, используй разработчик паттерн, описанный на лекции

    • Написать потоконебезопасный код (счетчик из слайдов/использование StringBuilder/что-то своё).
    • Убедиться, что результат некорректен.
    • Добиться корректности используя lock из стандартной библиотеки Java.
    • Релизовать свой lock, используя алгоритм Петерсона.
    • Заменить использование встроенного lock на свой.
    • Проверить, сохранится ли корректноть программы. Отчетность - скриншоты вывода каждой из версий программы. Алгоритм Петерсона очень вероятно на современной архитектуре работать не будет. Не ищите ошибку часами.
  2. Проверить измерениями, что графики производительности локов TAS и TTAS похожи на предсказанные теорией. Примечание: указанные локи реализовать, как на слайдах. Атомарный bool использовать из стандартной библиотеки Java.

© 2014-2018 HwProj