projects:libcds:tasks
Differences
This shows you the differences between two versions of the page.
Both sides previous revisionPrevious revisionNext revision | Previous revisionNext revisionBoth sides next revision | ||
courses:high_performance_computing:tasks_libcds [2016/08/07 01:38] – ↷ Page moved from high_performance_computing:tasks_libcds to courses:high_performance_computing:tasks_libcds kel | projects:libcds:tasks [2018/10/27 16:09] – kel | ||
---|---|---|---|
Line 1: | Line 1: | ||
- | ====== | + | ====== |
===== Профилирование и поиск ошибок ===== | ===== Профилирование и поиск ошибок ===== | ||
Найти, обосновать и исправить не менее 3 ошибок || пограммирвания (возможные dead lock, data race...). Предполагается использование автоматизированных стредств поиска, | Найти, обосновать и исправить не менее 3 ошибок || пограммирвания (возможные dead lock, data race...). Предполагается использование автоматизированных стредств поиска, | ||
Line 7: | Line 7: | ||
===== Алгоритмы ===== | ===== Алгоритмы ===== | ||
- | ==== A.Williams “C++ Concurrency in Action” - lock-free стек на shared_ptr ==== | ||
- | // | ||
- | |||
- | Алгоритм и его подробный анализ есть в книге. Требуется создать стек на C++11, используя оба алгоритма, | ||
- | |||
- | ==== A.Williams “C++ Concurrency in Action” - lock-free очередь на shared_ptr ==== | ||
- | // | ||
- | |||
- | Алгоритм и его подробный анализ есть в книге. Требуется создать очередь на C++11. Оценить, | ||
- | |||
==== [2011] Bar-Nissan, Hendler, Suissa. A dynamic elimination-combining stack algorithm.pdf ==== | ==== [2011] Bar-Nissan, Hendler, Suissa. A dynamic elimination-combining stack algorithm.pdf ==== | ||
// | // | ||
Line 36: | Line 26: | ||
Также: А также: [2010] Gidenstam, | Также: А также: [2010] Gidenstam, | ||
- | |||
- | ==== [2013] Henzinger, | ||
- | |||
- | // | ||
- | |||
- | Мне этот алгоритм очень хочется попробовать. Единственный минус — авторы не показали, | ||
- | |||
- | ==== [1995] Valois Lock-Free Linked Lists Using Compare-and_Swap.pdf ==== | ||
- | |||
- | // | ||
- | |||
- | Эта работа, | ||
==== [2003] Michael CAS-Based Lock-Free Algorithm for Shared Deques.pdf ==== | ==== [2003] Michael CAS-Based Lock-Free Algorithm for Shared Deques.pdf ==== | ||
Line 54: | Line 32: | ||
Реализовать описанный в статье алгоритм bounded deque. SMR здесь не требуется, | Реализовать описанный в статье алгоритм bounded deque. SMR здесь не требуется, | ||
- | |||
- | ==== [2014] Dodds, | ||
- | |||
- | // | ||
- | |||
- | Перспективный алгоритм построения lock-free стека, очереди, | ||
==== [2003] Gao, Groote, Hesselink Efficient almost wait-free parallel accessible dynamic Hashtables.pdf ==== | ==== [2003] Gao, Groote, Hesselink Efficient almost wait-free parallel accessible dynamic Hashtables.pdf ==== | ||
Line 81: | Line 53: | ||
Еще одна разновидность open-addressing hash table. Алгоритм не описывает расширение таблицы, | Еще одна разновидность open-addressing hash table. Алгоритм не описывает расширение таблицы, | ||
- | |||
- | ==== [2007] Herlihy, Lev, Luchangco, Shavit A Provably Correct Scalable Concurrent Skip List .pdf ==== | ||
- | |||
- | // | ||
- | |||
- | Skip-list, основанный на fine-grained locks (блокировка на уровне элементов — именно для такого класса алгоритмов интересно реализовать различные mutex' | ||
- | <code c++> | ||
- | struct node { | ||
- | … | ||
- | uint32_t height; | ||
- | node * tower; // только для узлов высотой > 4 | ||
- | node * next[4]; | ||
- | |||
- | node * next( uint32_t level ) | ||
- | { | ||
- | if ( level < 4 ) return next[level]; | ||
- | return tower[level – 4]; | ||
- | } | ||
- | }; | ||
- | </ | ||
- | |||
- | ==== [2008] Herlihy, | ||
- | |||
- | // | ||
- | |||
- | Интересный алгоритм open-addressing hash table. Похож на Cuckoo hashing, реализация которого есть в libcds. | ||
==== [2012] Crain, | ==== [2012] Crain, | ||
Line 119: | Line 65: | ||
В libcds уже есть HP- и RCU-based реализации (без helping' | В libcds уже есть HP- и RCU-based реализации (без helping' | ||
- | |||
- | ==== [2010] Bronson, | ||
- | |||
- | // | ||
- | |||
- | Реализация конкурентного AVL-tree, новый метод optimistic hand-over-hand locking. Проанализировать, | ||
==== [2011] Brown,Helga Non-blocking k-ary Search Trees.pdf ==== | ==== [2011] Brown,Helga Non-blocking k-ary Search Trees.pdf ==== | ||
Line 147: | Line 87: | ||
Реализация конкурентного trie. No comments. | Реализация конкурентного trie. No comments. | ||
+ | ===== Требующие доработки ===== | ||
+ | ==== [2007] Herlihy, Lev, Luchangco, Shavit A Provably Correct Scalable Concurrent Skip List .pdf ==== | ||
+ | > // | ||
+ | > [[https:// | ||
+ | |||
+ | Skip-list, основанный на fine-grained locks (блокировка на уровне элементов — именно для такого класса алгоритмов интересно реализовать различные mutex' | ||
+ | <code c++> | ||
+ | struct node { | ||
+ | … | ||
+ | uint32_t height; | ||
+ | node * tower; // только для узлов высотой > 4 | ||
+ | node * next[4]; | ||
+ | |||
+ | node * next( uint32_t level ) | ||
+ | { | ||
+ | if ( level < 4 ) return next[level]; | ||
+ | return tower[level – 4]; | ||
+ | } | ||
+ | }; | ||
+ | </ | ||
+ | |||
+ | ==== [2013] Henzinger, | ||
+ | > // | ||
+ | > [[https:// | ||
+ | |||
+ | Мне этот алгоритм очень хочется попробовать. Единственный минус — авторы не показали, | ||
+ | |||
+ | ==== [1995] Valois Lock-Free Linked Lists Using Compare-and_Swap.pdf ==== | ||
+ | > // | ||
+ | > [[https:// | ||
+ | |||
+ | Эта работа, | ||
+ | |||
+ | ==== [2008] Herlihy, | ||
+ | > // | ||
+ | > [[https:// | ||
+ | |||
+ | Интересный алгоритм open-addressing hash table. Похож на Cuckoo hashing, реализация которого есть в libcds. | ||
+ | |||
+ | ==== A.Williams “C++ Concurrency in Action” - lock-free очередь на shared_ptr ==== | ||
+ | > // | ||
+ | > [[https:// | ||
+ | |||
+ | Алгоритм и его подробный анализ есть в книге. Требуется создать очередь на C++11. Оценить, | ||
+ | |||
+ | ==== A.Williams “C++ Concurrency in Action” - lock-free стек на shared_ptr ==== | ||
+ | > // | ||
+ | > [[https:// | ||
+ | |||
+ | Алгоритм и его подробный анализ есть в книге. Требуется создать стек на C++11, используя оба алгоритма, | ||
+ | |||
+ | ==== [2014] Dodds, | ||
+ | > // | ||
+ | > [[https:// | ||
+ | |||
+ | Перспективный алгоритм построения lock-free стека, очереди, | ||
+ | |||
+ | ===== Реализованные ===== | ||
projects/libcds/tasks.txt · Last modified: 2019/02/04 20:12 by kel