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 revision Previous revision
Next revision
Previous revision
projects:libcds:tasks [2015/11/25 09:14]
kel
projects:libcds:tasks [2019/02/04 20:12] (current)
kel
Line 1: Line 1:
-====== ​Доработка библиотеки libcds ====== +====== ​Алгоритмы для доработки ​в libcds ====== 
-===== Профилирование и поиск ошибок ​===== +===== Требования к реализации ===== 
-Найти, обосновать и исправить ​не менее 3 ошибок || пограммирвания (возможные dead lock, data race...). Предполагается использование автоматизированных стредств поиска, таких как: +//К следующему семестру более явно написать ​формулировки пп. 4 и 9// 
-  - Valgrind //​helgrind//​ +  - Pull Request должен быть сливаем с текущей master-веткой репозитория 
-  - Intel Parallel Studio +  - Отсутствие закомментированных кусков кода 
-  - Google Thread Sanitizer... +  - Код написан в стиле и стандарте кодирования библиотеки 
- +  - Написан набор модульных ​и стресс-тестов (если структура данных стандартная,​ то тесты используются сущетвующие с регистрацией своей структуры данных) 
-===== Исследование реализаций ​на HTM ===== +  - Поддерживается интерфейс сбора статистики по контейнеруесли таковой есть в библиотеке для ​реализуемого типа контейнеров 
-Выбрать алгоритм и изменить его реализацию с использованием HTM, сравнить полученные результаты с оригинальной +  - Сборка и прогон ​тестов с активированными Address и Undefined Behavior Sanitizers не выдаёт никаких ошибок ("​-fsanitize=address,​undefined"​) 
- +  Тесты прогнаны с активированным Thread Sanitizer и по каждому предупреждению есть ​уверенность, что это не ошибка 
-===== Алгоритмы ===== +  - Тесты проанализированы сторонним средством поиска ошибок (например, Intel Parallel Studio) ​и также по каждому предупреждению есть ​уверенность, что это не ошибка 
-==== A.Williams “C++ Concurrency in Action” ​lock-free ​стек на shared_ptr ==== +  - После выполнения вышеуказанных пунктов ветка добавляется ​в CI и на всех поддерживаемых платформах ​все тесты проходят успешно
-//Сложность://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 28: Line 21:
   - Центральный стек — алгоритм Трейбера. Будет здорово,​ если в реализации класс стека будет вынесен в опции (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 105: Line 75:
 </​code>​ </​code>​
  
-==== [2008Herlihy,Shavit,Tzafrir Hopscotch Hashing.pdf ====+==== [2013Henzinger,Payer,Sezgin Replacing competition with cooperation to achieve scalable lock-free FIFO queues.pdf ==== 
 +> //​Сложность://​4 
 +> [[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 ​==== 
 +> //​Сложность://​2 
 +> [[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.1448432095.txt.gz · Last modified: 2015/11/25 09:14 by kel