Differences

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

--- high_performance_computing:tasks_libcds [2016/04/10 21:42] – kel
+++ projects:libcds:tasks [2017/09/20 00:59] – Убран алгоритм по причине уже его реализованности kel
@@ Line 1: / Line 1: @@
-====== Доработка библиотеки libcds ======
+====== Алгоритмы для доработки в libcds ======
 ===== Профилирование и поиск ошибок =====
 Найти, обосновать и исправить не менее 3 ошибок || пограммирвания (возможные dead lock, data race...). Предполагается использование автоматизированных стредств поиска, таких как:
@@ Line 7: / Line 7: @@
 ===== Алгоритмы =====
-==== A.Williams “C++ Concurrency in Action” - lock-free стек на shared_ptr ====
-//Сложность://1+
-Алгоритм и его подробный анализ есть в книге. Требуется создать стек на C++11, используя оба алгоритма, описанных в книге: на shared_ptr и split reference counting. Оценить, можно ли создать intrusive-версию.
-==== A.Williams “C++ Concurrency in Action” - lock-free очередь на shared_ptr ====
-//Сложность://2\\
-Алгоритм и его подробный анализ есть в книге. Требуется создать очередь на C++11. Оценить, можно ли создать intrusive-версию.
 ==== [2011] Bar-Nissan, Hendler, Suissa. A dynamic elimination-combining stack algorithm.pdf ====
 //Сложность://3\\
@@ Line 54: / Line 44: @@
 Реализовать описанный в статье алгоритм bounded deque. SMR здесь не требуется, так как deque основана на массиве.
-==== [2014] Dodds,Haas,Kirsch Fast Concurrent Data-Structures Through Explicit Timestamping.pdf ====
-//Сложность://4\\
-Перспективный алгоритм построения lock-free стека, очереди, deque. Должен обеспечивать очень хорошую производительность для push-операций, так как push производится в локальный для потока storage. Псевдокод основан на tagged pointers, требуется применить какой-либо другой SMR – Hazard Pointers, reference counting.
 ==== [2003] Gao, Groote, Hesselink Efficient almost wait-free parallel accessible dynamic Hashtables.pdf ====
@@ Line 119: / Line 103: @@
 В libcds уже есть HP- и RCU-based реализации (без helping'а), требуется сделать append-only версию (без GC – cds::gc::nogc), то есть версию без возможности удаления элементов. Попробовать реализовать helping (будет хорошо, если helping будет включаться отдельным флагом в traits).
-==== [2010] Bronson,Casper,Chafi,Olukotun A Practical Concurrent Binary Search Tree.pdf ====
-//Сложность://7\\
-Реализация конкурентного AVL-tree, новый метод optimistic hand-over-hand locking. Проанализировать, какой SMR подходит (HP, RCU, оба), либо же алгоритм не требует никакой SMR схемы.
 ==== [2011] Brown,Helga Non-blocking k-ary Search Trees.pdf ====
@@ Line 147: / Line 125: @@
 Реализация конкурентного trie. No comments.
+===== Требующие доработки =====
+==== A.Williams “C++ Concurrency in Action” - lock-free очередь на shared_ptr ====
+> //Сложность://2
+> [[https://github.com/khizmax/libcds/pull/72|Pull request]]
+Алгоритм и его подробный анализ есть в книге. Требуется создать очередь на C++11. Оценить, можно ли создать intrusive-версию.
+==== A.Williams “C++ Concurrency in Action” - lock-free стек на shared_ptr ====
+> //Сложность://1+
+> [[https://github.com/khizmax/libcds/pull/73|Pull request]]
+Алгоритм и его подробный анализ есть в книге. Требуется создать стек на C++11, используя оба алгоритма, описанных в книге: на shared_ptr и split reference counting. Оценить, можно ли создать intrusive-версию.
+==== [2014] Dodds,Haas,Kirsch Fast Concurrent Data-Structures Through Explicit Timestamping.pdf ====
+> //Сложность://4\\
+> [[https://github.com/khizmax/libcds/pull/55|Pull request]]
+Перспективный алгоритм построения lock-free стека, очереди, deque. Должен обеспечивать очень хорошую производительность для push-операций, так как push производится в локальный для потока storage. Псевдокод основан на tagged pointers, требуется применить какой-либо другой SMR – Hazard Pointers, reference counting.
+===== Реализованные =====