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 [2018/10/27 16:09]
kel
projects:libcds:tasks [2019/02/04 20:12] (current)
kel
Line 1: Line 1:
 ====== Алгоритмы для доработки в libcds ====== ====== Алгоритмы для доработки в libcds ======
-===== Профилирование и поиск ошибок ===== +===== Требования к реализации ===== 
-Найтиобосновать и исправить не менее ​ошибок ​|| пограммирвания (возможные ​dead lockdata race...). Предполагается использование автоматизированных стредств поиска,​ таких как: +//К следующему семестру более явно написать формулировки пп. 4 и 9// 
-  - Valgrind //​helgrind//​ +  - Pull Request должен быть сливаем с текущей master-веткой репозитория 
-  - Intel Parallel Studio +  - Отсутствие закомментированных ​кусков кода 
-  - Google Thread Sanitizer...+  - Код написан в стиле и стандарте кодирования ​библиотеки 
 +  - Написан набор модульных и стресс-тестов (если структура данных стандартная,​ то тесты используются сущетвующие с регистрацией своей структуры данных) 
 +  - Поддерживается интерфейс сбора статистики по контейнеру, если таковой есть в библиотеке для ​реализуемого типа контейнеров 
 +  - Сборка и прогон тестов с активированными Address и Undefined Behavior Sanitizers не выдаёт никаких ошибок ("​-fsanitize=address,undefined"​) 
 +  - Тесты ​прогнаны с активированным Thread Sanitizer ​и по каждому предупреждению есть уверенность,​ что это не ошибка 
 +  - Тесты проанализированы сторонним средством поиска ​ошибок (напримерIntel Parallel Studio) и также по каждому предупреждению есть уверенность,​ что это не ошибка 
 +  - После выполнения вышеуказанных пунктов ветка добавляется в CI и на всех поддерживаемых платформах все тесты проходят успешно
  
-===== Алгоритмы =====+===== Нереализованные =====
 ==== [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 14: Line 20:
   - Распределения динамической памяти (allocation) под структуры multiOp быть не должно. Лучшим вариантом будет, если multiOp создаются на стеке, но в этом случае могут быть серьезные проблемы с временем жизни, - обращение к разрушенным данным и пр.   - Распределения динамической памяти (allocation) под структуры multiOp быть не должно. Лучшим вариантом будет, если multiOp создаются на стеке, но в этом случае могут быть серьезные проблемы с временем жизни, - обращение к разрушенным данным и пр.
   - Центральный стек — алгоритм Трейбера. Будет здорово,​ если в реализации класс стека будет вынесен в опции (traits) класса DECStack.   - Центральный стек — алгоритм Трейбера. Будет здорово,​ если в реализации класс стека будет вынесен в опции (traits) класса DECStack.
- 
-==== [2014] Henzinger, Kirsch, Payer, Sezgin, Sokolova Quantitative Relaxation of Concurrent Data Structures.pdf ==== 
- 
-//​Сложность://​3\\ 
- 
-Сегментированный стек. В статье приводится псевдокод для tagged pointers (указатель + версия). Следует реализовать его на Hazard Pointer, intrusive и stl-like версию. Размер сегмента — степень двойки,​ задается в конструкторе. Оценить,​ возможно ли сделать оптимизацию — не удалять сегмент,​ а вести некоторый free-list нескольких удаленных сегментов. ​ 
- 
-==== [2010] Gidenstam,​Sundell,​Tsigas Cache-Aware Lock-free Queues for Multiple Producers-Consumers and Weak Memory Consistency.pdf ==== 
- 
-//​Сложность://​4\\ 
- 
-Также: А также: [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 версии. 
- 
-==== [2003] Michael CAS-Based Lock-Free Algorithm for Shared Deques.pdf ==== 
- 
-//​Сложность://​3\\ 
- 
-Реализовать описанный в статье алгоритм bounded deque. SMR здесь не требуется,​ так как deque основана на массиве. 
- 
-==== [2003] Gao, Groote, Hesselink 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 ==== ==== [2005] Purcell, Harris Non-blocking Hashtables with open addressing.pdf ====
Line 59: Line 32:
  
 Ещё одна реализация skip-list. Алгоритм интересен тем, что на нулевом уровне узлы связаны в double-linked list. Авторы не говорят,​ применим ли HP к их алгоритму,​ вместо этого они предлагают использовать reference counting или кратко описанный ими epoch-based подход. Требуется понять,​ можно ли применить HP и/или RCU. Ещё одна реализация skip-list. Алгоритм интересен тем, что на нулевом уровне узлы связаны в double-linked list. Авторы не говорят,​ применим ли HP к их алгоритму,​ вместо этого они предлагают использовать reference counting или кратко описанный ими epoch-based подход. Требуется понять,​ можно ли применить HP и/или RCU.
- 
-==== [2010] Ellen,​Fatourou,​Ruppert,​vanBreugel Non-blocking Binary Search Trees.pdf ==== 
- 
-//​Сложность://​2+\\ 
- 
-В libcds уже есть HP- и RCU-based реализации (без helping'​а),​ требуется сделать append-only версию (без GC – cds::​gc::​nogc),​ то есть версию без возможности удаления элементов. Попробовать реализовать helping (будет хорошо,​ если helping будет включаться отдельным флагом в traits). ​ 
  
 ==== [2011] Brown,Helga Non-blocking k-ary Search Trees.pdf ==== ==== [2011] Brown,Helga Non-blocking k-ary Search Trees.pdf ====
Line 125: Line 92:
  
 Интересный алгоритм open-addressing hash table. Похож на Cuckoo hashing, реализация которого есть в libcds. ​ Интересный алгоритм open-addressing hash table. Похож на Cuckoo hashing, реализация которого есть в libcds. ​
 +
 +==== [2010] Ellen,​Fatourou,​Ruppert,​vanBreugel Non-blocking Binary Search Trees.pdf ====
 +> //​Сложность://​2+
 +> [[https://​github.com/​khizmax/​libcds/​pull/​104|Pull request]]
 +
 +В libcds уже есть HP- и RCU-based реализации (без helping'​а),​ требуется сделать append-only версию (без GC – cds::​gc::​nogc),​ то есть версию без возможности удаления элементов. Попробовать реализовать helping (будет хорошо,​ если helping будет включаться отдельным флагом в traits). ​
  
 ==== A.Williams “C++ Concurrency in Action” - lock-free очередь на shared_ptr ==== ==== A.Williams “C++ Concurrency in Action” - lock-free очередь на shared_ptr ====
Line 143: Line 116:
  
 Перспективный алгоритм построения lock-free стека, очереди,​ deque. Должен обеспечивать очень хорошую производительность для push-операций,​ так как push производится в локальный для потока storage. Псевдокод основан на tagged pointers, требуется применить какой-либо другой SMR – Hazard Pointers, reference counting. Перспективный алгоритм построения 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 ====
 +> //​Сложность://​5\\
 +> [[https://​github.com/​khizmax/​libcds/​pull/​102|Pull request]]
 +
 +Интересный алгоритм 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.
 +
 +==== [2010] Gidenstam,​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]]
 +
 +Также: А также: [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 версии.
 +
 +==== [2014] Henzinger, Kirsch, Payer, Sezgin, Sokolova Quantitative Relaxation of Concurrent Data Structures.pdf ====
 +> //​Сложность://​3\\
 +> [[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.1540645799.txt.gz · Last modified: 2018/10/27 16:09 by kel