Open Source & Linux Lab

It's better when it's simple

User Tools

Site Tools


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/28 00:36] kel
Line 1: Line 1:
-====== Доработка библиотеки libcds ====== +====== Алгоритмы для доработки в libcds ====== 
-===== Профилирование и поиск ошибок ===== +===== Требования к реализации ===== 
-Найти, обосновать и исправить не менее 3 ошибок || пограммирвания (возможные dead lock, data race...). Предполагается использование автоматизированных стредств поиска, таких как: +  - Pull Request должен быть сливаем с текущей master-веткой репозитория 
-  - Valgrind //helgrind// +  - Отсутствие закомментированных кусков кода 
-  - Intel Parallel Studio +  - Код написан в стиле и стандарте кодирования библиотеки 
-  - Google Thread Sanitizer... +  - Написан набор модульных и стресс-тестов (если структура данных стандартная, то тесты используются сущетвующие с регистрацией своей структуры данных) 
- +  - Поддерживается интерфейс сбора статистики по контейнеру, если таковой есть в библиотеке для реализуемого типа контейнеров 
-===== Алгоритмы ===== +  - Сборка и прогон тестов с активированными Address и Undefined Behavior Sanitizers не выдаёт никаких ошибок ("-fsanitize=address,undefined"
-==== A.Williams “C++ Concurrency in Action” - lock-free стек на shared_ptr ==== +  - Тесты прогнаны с активированным Thread Sanitizer и по каждому предупреждению есть уверенность, что это не ошибка 
-//Сложность://1+ +  Тесты проанализированы сторонним средством поиска ошибок (например, Intel Parallel Studio) и также по каждому предупреждению есть уверенность, что это не ошибка 
- +  - После выполнения вышеуказанных пунктов ветка добавляется в CI и на всех поддерживаемых платформах все тесты проходят успешно
-Алгоритм и его подробный анализ есть в книге. Требуется создать стек на 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 25: Line 20:
   - Центральный стек — алгоритм Трейбера. Будет здорово, если в реализации класс стека будет вынесен в опции (traits) класса DECStack.   - Центральный стек — алгоритм Трейбера. Будет здорово, если в реализации класс стека будет вынесен в опции (traits) класса DECStack.
  
-==== [2014HenzingerKirsch, Payer, Sezgin, Sokolova Quantitative Relaxation of Concurrent Data Structures.pdf ====+==== [2005PurcellHarris Non-blocking Hashtables with open addressing.pdf ====
  
-//Сложность://3\\+//Сложность://5+\\
  
-Сегментированный стек. В статье приводится псевдокод для tagged pointers (указатель + версия)Следует реализовать его на Hazard Pointer, intrusive и stl-like версию. Размер сегмента — степень двойки, задается в конструкторе. Оценить, возможно ли сделать оптимизацию — не удалять сегмент, а вести некоторый free-list нескольких удаленных сегментов+Еще одна разновидность open-addressing hash tableАлгоритм не описывает расширение таблицы, предлагается использовать метод из предыдущей работы ([2003] Gao, Groote, Hesselink Efficient almost wait-free parallel accessible dynamic Hashtables.pdf)
  
-==== [2010Gidenstam,Sundell,Tsigas Cache-Aware Lock-free Queues for Multiple Producers-Consumers and Weak Memory Consistency.pdf ====+==== [2012Crain,Gramoli,Raynal A Contention-Friendly, Non-Blocking Skip List.pdf ====
  
-//Сложность://4\\+//Сложность://6\\
  
-Также: А также: [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 версии.+Ещё одна реализация skip-list. Алгоритм интересен тем, что на нулевом уровне узлы связаны в double-linked list. Авторы не говорятприменим ли HP к их алгоритму, вместо этого они предлагают использовать reference counting или кратко описанный ими epoch-based подходТребуется понять, можно ли применить HP и/или RCU.
  
-==== [2013Henzinger,Payer,Sezgin Replacing competition with cooperation to achieve scalable lock-free FIFO queues.pdf ====+==== [2011Brown,Helga Non-blocking k-ary Search Trees.pdf ====
  
-//Сложность://4\\+//Сложность://7\\
  
-Мне этот алгоритм очень хочется попробовать. Единственный минус — авторы не показаликак использовать технику HP, только намекнули в нескольких предложениях. Требуется адаптировать алгоритм под Hazard Pointer и/или связаться с авторами, запросив пояснений.+Развитие подхода [2010] Ellen,Fatourou,Ruppert,vanBreugel Non-blocking Binary Search Trees.pdf на k-арные деревьяСделать без helping'а, оценитьво что выливается реализация helping'а и стоит ли его вообще делать.
  
-==== [1995Valois Lock-Free Linked Lists Using Compare-and_Swap.pdf ====+==== [2012Afek,Kaplan,Korenfeld,Morrison,Tarjan CBTree A Practical Concurrent Self-adusting Search Tree.pdf ====
  
-//Сложность://3+\\+//Сложность://7+\\
  
-Эта работа, несмотря на свою «старость», интересна тем, что позволяет сделать полноценные итераторы по 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.+[2012] Korenfeld CBTree - A Practical Concurrent Self-Adjusting Search Tree.pdf 
 +Разновидность самобалансирующегося деревапостроенного с использованием техники hand-over-hand locking. Проанализировать, какой SMR подходит (HP, RCU, оба)либо же алгоритм не требует никакой SMR схемы.
  
-==== [2003Michael CAS-Based Lock-Free Algorithm for Shared Deques.pdf ====+==== [2011Prokopec,Bagwell,Odersky Cache-Aware Lock-Free Concurrent Hash Tries.pdf ====
  
-//Сложность://3\\+//Сложность://8\\
  
-Реализовать описанный в статье алгоритм bounded deque. SMR здесь не требуется, так как deque основана на массиве. +[2011Prokopec,Bagwell,Odersky Lock-Free Resizable Concurrent Tries.pdf 
- +[2011Prokopec,Bronson,Bagwell,Odersky Concurrent Tries with Efficient Non-Blocking Snapshots.pdf 
-==== [2014Dodds,Haas,Kirsch Fast Concurrent Data-Structures Through Explicit Timestamping.pdf ==== +Реализация конкурентного trieNo comments.
- +
-//Сложность://4\\ +
- +
-Перспективный алгоритм построения lock-free стека, очереди, deque. Должен обеспечивать очень хорошую производительность для push-операций, так как push производится в локальный для потока storage. Псевдокод основан на tagged pointers, требуется применить какой-либо другой SMR – Hazard Pointers, reference counting. +
- +
-==== [2003GaoGrooteHesselink Efficient almost wait-free parallel accessible dynamic Hashtables.pdf ==== +
- +
-//Сложность://5\\ +
- +
-Интересный алгоритм open-addressing hash table. Следует сделать intrusive-вариант: храним указатели на данные, считаем, что распределять память под данные не нужно. +
-Алгоритм описан достаточно хорошо, но непривычно. +
-Замечания: +
-  - Понять, где следует применять атомарные операции. В псевдокоде это отмечено скобками < >: +
-    * < a := b > => atomic load, atomic store +
-    * < if a == 0 then a := b > => a.CAS( 0, b ) +
-  - Псевдокод описан в предположении, что имеется P потоков (процессов), работающих с hash  set. Попробовать избавиться от P. Если не получится — P должен быть параметром конструктора. Для thread-local data использовать TLS. Реализация должна учитывать, что P может быть достигнуто — в этом случае либо выбрасывать исключение (плохо), либо каким-то образом дожидаться освобождения слота (лучше). +
-  - К данным, хранимым в hash table, следует применять Hazard Pointer. Для управления внутренними структурами алгоритм использует разновидность refCount. +
- +
-Развитие: если можно выделить алгоритм расширения hash-таблицы в отдельную программную сущность (класс), то его в принципе можно применить к любым алгоритмам open-addressing, например, к cuckoo hashing. +
- +
-==== [2005] Purcell, Harris Non-blocking Hashtables with open addressing.pdf ==== +
- +
-//Сложность://5+\\ +
- +
-Еще одна разновидность 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 ==== ==== [2007] Herlihy, Lev, Luchangco, Shavit A Provably Correct Scalable Concurrent Skip List .pdf ====
- +//Сложность://4+ 
-//Сложность://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: 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:
Line 102: Line 74:
 </code> </code>
  
-==== [2008Herlihy,Shavit,Tzafrir Hopscotch Hashing.pdf ====+==== [2013Henzinger,Payer,Sezgin Replacing competition with cooperation to achieve scalable lock-free FIFO queues.pdf ==== 
 +> //Сложность://
 +> [[https://github.com/khizmax/libcds/pull/108|Pull request]]
  
-//Сложность://5+\\+Мне этот алгоритм очень хочется попробовать. Единственный минус — авторы не показали, как использовать технику HP, только намекнули в нескольких предложениях. Требуется адаптировать алгоритм под Hazard Pointer и/или связаться с авторами, запросив пояснений.
  
-Интересный алгоритм open-addressing hash tableПохож на Cuckoo hashing, реализация которого есть в libcds+==== [1995] Valois Lock-Free Linked Lists Using Compare-and_Swap.pdf ==== 
 +> //Сложность://3+ 
 +> [[https://github.com/khizmax/libcds/pull/107|Pull request]]
  
-==== [2012] Crain,Gramoli,Raynal A Contention-FriendlyNon-Blocking Skip List.pdf ====+Эта работанесмотря на свою «старость»интересна тем, что позволяет сделать полноценные итераторы по lock-free структуре. На основе описанного алгоритма списка можно построить hash-map (MichaelHashSet/MapSplitListSet/Map – эти структуры в libcds как параметр принимают реализацию списка) или даже SkipList с возможностью безопасной итерации, что очень ценно. Не забывать, что в данном алгоритме есть ошибка — см. [1995] Michael, Scott Correction of a Memory Management Method for Lock-Free Data Structures.pdf.
  
-//Сложность://6\\+==== [2008] Herlihy,Shavit,Tzafrir Hopscotch Hashing.pdf ==== 
 +//Сложность://5+ 
 +> [[https://github.com/khizmax/libcds/pull/106|Pull request]]
  
-Ещё одна реализация skip-list. Алгоритм интересен тем, что на нулевом уровне узлы связаны в double-linked list. Авторы не говорят, применим ли HP к их алгоритму, вместо этого они предлагают использовать reference counting или кратко описанный ими epoch-based подход. Требуется понять, можно ли применить HP и/или RCU.+Интересный алгоритм open-addressing hash table. Похож на Cuckoo hashing, реализация которого есть в libcds
  
 ==== [2010] Ellen,Fatourou,Ruppert,vanBreugel Non-blocking Binary Search Trees.pdf ==== ==== [2010] Ellen,Fatourou,Ruppert,vanBreugel Non-blocking Binary Search Trees.pdf ====
- +//Сложность://2+ 
-//Сложность://2+\\+> [[https://github.com/khizmax/libcds/pull/104|Pull request]]
  
 В 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 Practical Concurrent Binary Search Tree.pdf ====+==== A.Williams “C++ Concurrency in Action” - lock-free очередь на shared_ptr ==== 
 +> //Сложность://
 +> [[https://github.com/khizmax/libcds/pull/72|Pull request]]
  
-//Сложность://7\\+Алгоритм и его подробный анализ есть в книге. Требуется создать очередь на C++11. Оценить, можно ли создать intrusive-версию.
  
-Реализация конкурентного AVL-tree, новый метод optimistic hand-over-hand locking. Проанализировать, какой SMR подходит (HP, RCU, оба), либо же алгоритм не требует никакой SMR схемы.+==== A.Williams “C++ Concurrency in Action” lock-free стек на shared_ptr ==== 
 +> //Сложность://1+ 
 +> [[https://github.com/khizmax/libcds/pull/73|Pull request]]
  
-==== [2011] Brown,Helga Non-blocking k-ary Search Trees.pdf ====+Алгоритм и его подробный анализ есть в книге. Требуется создать стек на C++11используя оба алгоритма, описанных в книге: на shared_ptr и split reference counting. Оценить, можно ли создать intrusive-версию.
  
-//Сложность://7\\+==== [2014] Dodds,Haas,Kirsch Fast Concurrent Data-Structures Through Explicit Timestamping.pdf ==== 
 +//Сложность://4\\ 
 +> [[https://github.com/khizmax/libcds/pull/55|Pull request]]
  
-Развитие подхода [2010] Ellen,Fatourou,Ruppert,vanBreugel Non-blocking Binary Search Trees.pdf на k-арные деревья. Сделать без helping'а, оценить, во что выливается реализация helping'а и стоит ли его вообще делать.+Перспективный алгоритм построения lock-free стека, очереди, deque. Должен обеспечивать очень хорошую производительность для push-операций, так как push производится в локальный для потока storage. Псевдокод основан на tagged pointers, требуется применить какой-либо другой SMR – Hazard Pointers, reference counting.
  
-==== [2012Afek,Kaplan,Korenfeld,Morrison,Tarjan CBTree A Practical Concurrent Self-adusting Search Tree.pdf ====+==== [2003GaoGrooteHesselink Efficient almost wait-free parallel accessible dynamic Hashtables.pdf ==== 
 +> //Сложность://5\\ 
 +> [[https://github.com/khizmax/libcds/pull/102|Pull request]]
  
-//Сложность://7+\\+Интересный алгоритм open-addressing hash table. Следует сделать intrusive-вариант: храним указатели на данные, считаем, что распределять память под данные не нужно. 
 +Алгоритм описан достаточно хорошо, но непривычно. 
 +Замечания: 
 +  - Понять, где следует применять атомарные операции. В псевдокоде это отмечено скобками < >: 
 +    * < a := b > => atomic load, atomic store 
 +    * < if a == 0 then a := b > => a.CAS( 0, b ) 
 +  - Псевдокод описан в предположении, что имеется P потоков (процессов), работающих с hash  set. Попробовать избавиться от P. Если не получится — P должен быть параметром конструктора. Для thread-local data использовать TLS. Реализация должна учитывать, что P может быть достигнуто — в этом случае либо выбрасывать исключение (плохо), либо каким-то образом дожидаться освобождения слота (лучше). 
 +  - К данным, хранимым в hash table, следует применять Hazard Pointer. Для управления внутренними структурами алгоритм использует разновидность refCount.
  
-[2012] Korenfeld CBTree - A Practical Concurrent Self-Adjusting Search Tree.pdf +Развитие: если можно выделить алгоритм расширения hash-таблицы в отдельную программную сущность (класс), то его в принципе можно применить к любым алгоритмам open-addressing, напримерк cuckoo hashing.
-Разновидность самобалансирующегося дерева, построенного с использованием техники hand-over-hand locking. Проанализироватькакой SMR подходит (HP, RCU, оба), либо же алгоритм не требует никакой SMR схемы.+
  
-==== [2011Prokopec,Bagwell,Odersky Cache-Aware Lock-Free Concurrent Hash Tries.pdf ====+==== [2010Gidenstam,Sundell,Tsigas Cache-Aware Lock-free Queues for Multiple Producers-Consumers and Weak Memory Consistency.pdf ==== 
 +> //Сложность://4\\ 
 +> [[https://github.com/khizmax/libcds/pull/100|Pull request]]
  
-//Сложность://8\\+Также: А также: [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 версии.
  
-[2011Prokopec,Bagwell,Odersky Lock-Free Resizable Concurrent Tries.pdf +==== [2014HenzingerKirschPayerSezginSokolova Quantitative Relaxation of Concurrent Data Structures.pdf ==== 
-[2011] Prokopec,Bronson,Bagwell,Odersky Concurrent Tries with Efficient Non-Blocking Snapshots.pdf +> //Сложность://3\\ 
-Реализация конкурентного trie. No comments.+> [[https://github.com/khizmax/libcds/pull/98|Pull request]]
  
 +Сегментированный стек. В статье приводится псевдокод для tagged pointers (указатель + версия). Следует реализовать его на Hazard Pointer, intrusive и stl-like версию. Размер сегмента — степень двойки, задается в конструкторе. Оценить, возможно ли сделать оптимизацию — не удалять сегмент, а вести некоторый free-list нескольких удаленных сегментов. 
  
 +===== Реализованные =====
 +==== [2003] Michael CAS-Based Lock-Free Algorithm for Shared Deques.pdf ====
 +> //Сложность://3\\
 +> [[https://github.com/khizmax/libcds/pull/88|Pull request]]
 +
 +Реализовать описанный в статье алгоритм bounded deque. SMR здесь не требуется, так как deque основана на массиве.
projects/libcds/tasks.txt · Last modified: 2019/02/04 20:12 by kel