Open Source & Linux Lab

It's better when it's simple

User Tools

Site Tools

You are here: О нас » Проекты » Библиотека конкурентных структур данных » Алгоритмы для доработки в libcds
projects:libcds:tasks

Differences

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

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision		Previous revision
Next revisionBoth sides next revision
projects:libcds:tasks [2016/08/13 20:57] – ↷ Page moved and renamed from courses:high_performance_computing:tasks_libcds to projects:libcds:tasks kelprojects:libcds:tasks [2018/10/27 16:09] – kel
Line 1: Line 1:
-====== Доработка библиотеки libcds ======+====== Алгоритмы для доработки в libcds ======
 ===== Профилирование и поиск ошибок ===== ===== Профилирование и поиск ошибок =====
 Найти, обосновать и исправить не менее 3 ошибок || пограммирвания (возможные dead lock, data race...). Предполагается использование автоматизированных стредств поиска, таких как: Найти, обосновать и исправить не менее 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 ==== ==== [2011] Bar-Nissan, Hendler, Suissa. A dynamic elimination-combining stack algorithm.pdf ====
 //Сложность://3\\ //Сложность://3\\
Line 36: Line 26:
  
 Также: А также: [2010] Gidenstam,Sundell,Tsigas Efficient Lock-Free Queues that Mind the Cache.pdf. Алгоритм интересен тем, что память выделяется под блок элементов, как в std::deque, что может значительно увеличить производительность stl-like очереди. Оценить, можно ли реализовать этот алгоритм на Hazard Pointer. Алгоритм существенно полагается на разработанную авторами SMR схему — помесь HP и reference counting – в части управления списком блоков. Попробовать использовать для блоков shared_ptr + HP. Создать intrusive и stl-like версии. Также: А также: [2010] Gidenstam,Sundell,Tsigas Efficient Lock-Free Queues that Mind the Cache.pdf. Алгоритм интересен тем, что память выделяется под блок элементов, как в std::deque, что может значительно увеличить производительность stl-like очереди. Оценить, можно ли реализовать этот алгоритм на Hazard Pointer. Алгоритм существенно полагается на разработанную авторами SMR схему — помесь HP и reference counting – в части управления списком блоков. Попробовать использовать для блоков shared_ptr + HP. Создать intrusive и stl-like версии.
- 
-==== [2013] Henzinger,Payer,Sezgin Replacing competition with cooperation to achieve scalable lock-free FIFO queues.pdf ==== 
- 
-//Сложность://4\\ 
- 
-Мне этот алгоритм очень хочется попробовать. Единственный минус — авторы не показали, как использовать технику HP, только намекнули в нескольких предложениях. Требуется адаптировать алгоритм под Hazard Pointer и/или связаться с авторами, запросив пояснений. 
- 
-==== [1995] Valois Lock-Free Linked Lists Using Compare-and_Swap.pdf ==== 
- 
-//Сложность://3+\\ 
- 
-Эта работа, несмотря на свою «старость», интересна тем, что позволяет сделать полноценные итераторы по lock-free структуре. На основе описанного алгоритма списка можно построить hash-map (MichaelHashSet/Map, SplitListSet/Map – эти структуры в libcds как параметр принимают реализацию списка) или даже SkipList с возможностью безопасной итерации, что очень ценно. Не забывать, что в данном алгоритме есть ошибка — см. [1995] Michael, Scott Correction of a Memory Management Method for Lock-Free Data Structures.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 здесь не требуется, так как deque основана на массиве. Реализовать описанный в статье алгоритм 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 ==== ==== [2003] Gao, Groote, Hesselink Efficient almost wait-free parallel accessible dynamic Hashtables.pdf ====
Line 81: Line 53:
  
 Еще одна разновидность open-addressing hash table. Алгоритм не описывает расширение таблицы, предлагается использовать метод из предыдущей работы ([2003] Gao, Groote, Hesselink Efficient almost wait-free parallel accessible dynamic Hashtables.pdf).  Еще одна разновидность open-addressing hash table. Алгоритм не описывает расширение таблицы, предлагается использовать метод из предыдущей работы ([2003] Gao, Groote, Hesselink Efficient almost wait-free parallel accessible dynamic Hashtables.pdf). 
- 
-==== [2007] Herlihy, Lev, Luchangco, Shavit A Provably Correct Scalable Concurrent Skip List .pdf ==== 
- 
-//Сложность://4+\\ 
- 
-Skip-list, основанный на fine-grained locks (блокировка на уровне элементов — именно для такого класса алгоритмов интересно реализовать различные mutex'ы). Интересная и относительно простая реализация skip-list. Node сделать аналогично тому, как сделано в libcds SkipListSet. Можно подумать над оптимизацией для «невысоких» узлов: для узла высотой 1 не выделяется никакой памяти под башню (у него нет башни), 50% узлов в skip-list имеют высоту 1; хотелось бы для узлов высотой <= 4 не распределять память под башни, а использовать какой-то pre-allocated storage. Тем самым для 50 + 25 + 12,5 + 6,25 = 93.75% узлов не будет аллокаций, что хорошо должно сказаться на масштабируемости. Можно попробовать все узлы распределять высотой 4: 
-<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]; 
- } 
-}; 
-</code> 
- 
-==== [2008] Herlihy,Shavit,Tzafrir Hopscotch Hashing.pdf ==== 
- 
-//Сложность://5+\\ 
- 
-Интересный алгоритм open-addressing hash table. Похож на Cuckoo hashing, реализация которого есть в libcds.  
  
 ==== [2012] Crain,Gramoli,Raynal A Contention-Friendly, Non-Blocking Skip List.pdf ==== ==== [2012] Crain,Gramoli,Raynal A Contention-Friendly, Non-Blocking Skip List.pdf ====
Line 119: Line 65:
  
 В libcds уже есть HP- и RCU-based реализации (без helping'а), требуется сделать append-only версию (без GC – cds::gc::nogc), то есть версию без возможности удаления элементов. Попробовать реализовать helping (будет хорошо, если helping будет включаться отдельным флагом в traits).  В 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 ==== ==== [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 ====
 +> //Сложность://4+
 +> [[https://github.com/khizmax/libcds/pull/109|Pull request]]
 +
 +Skip-list, основанный на fine-grained locks (блокировка на уровне элементов — именно для такого класса алгоритмов интересно реализовать различные mutex'ы). Интересная и относительно простая реализация skip-list. Node сделать аналогично тому, как сделано в libcds SkipListSet. Можно подумать над оптимизацией для «невысоких» узлов: для узла высотой 1 не выделяется никакой памяти под башню (у него нет башни), 50% узлов в skip-list имеют высоту 1; хотелось бы для узлов высотой <= 4 не распределять память под башни, а использовать какой-то pre-allocated storage. Тем самым для 50 + 25 + 12,5 + 6,25 = 93.75% узлов не будет аллокаций, что хорошо должно сказаться на масштабируемости. Можно попробовать все узлы распределять высотой 4:
 +<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];
 + }
 +};
 +</code>
 +
 +==== [2013] Henzinger,Payer,Sezgin Replacing competition with cooperation to achieve scalable lock-free FIFO queues.pdf ====
 +> //Сложность://4
 +> [[https://github.com/khizmax/libcds/pull/108|Pull request]]
 +
 +Мне этот алгоритм очень хочется попробовать. Единственный минус — авторы не показали, как использовать технику HP, только намекнули в нескольких предложениях. Требуется адаптировать алгоритм под Hazard Pointer и/или связаться с авторами, запросив пояснений.
 +
 +==== [1995] Valois Lock-Free Linked Lists Using Compare-and_Swap.pdf ====
 +> //Сложность://3+
 +> [[https://github.com/khizmax/libcds/pull/107|Pull request]]
 +
 +Эта работа, несмотря на свою «старость», интересна тем, что позволяет сделать полноценные итераторы по lock-free структуре. На основе описанного алгоритма списка можно построить hash-map (MichaelHashSet/Map, SplitListSet/Map – эти структуры в libcds как параметр принимают реализацию списка) или даже SkipList с возможностью безопасной итерации, что очень ценно. Не забывать, что в данном алгоритме есть ошибка — см. [1995] Michael, Scott Correction of a Memory Management Method for Lock-Free Data Structures.pdf.
 +
 +==== [2008] Herlihy,Shavit,Tzafrir Hopscotch Hashing.pdf ====
 +> //Сложность://5+
 +> [[https://github.com/khizmax/libcds/pull/106|Pull request]]
 +
 +Интересный алгоритм open-addressing hash table. Похож на Cuckoo hashing, реализация которого есть в libcds. 
 +
 +==== 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.
 +
 +===== Реализованные =====
  
projects/libcds/tasks.txt · Last modified: 2019/02/04 20:12 by kel