1 Разработка и анализ параллельных поисковых структур данных, не чувствительных к размеру кеша Акишев Искандер Рустемович Научный руководитель: Елизаров Роман Анатольевич СПб ГУ ИТМО, 2008

2 Классический анализ алгоритмов Модель RAM:

3 Реальные системы 1. Наличие кеш- памяти

4 Реальные системы 1. Наличие кеш- памяти Желание научиться располагать близкие элементы данных близко Следствие: указатели – «плохо» массивы – «хорошо»

5 Реальные системы 2. Параллельные системы

6 Реальные системы 2. Параллельные системы Необходимость синхронизации Опасности блокировок Недетерминизм … Значительное усложнение алгоритмов:

7 Цель: Создание алгоритмов, которые учитывают эти особенности и, как следствие, эффективны на практике.

8 Основные идеи 1. Michael, Scott, 1996 Быстрый и простой алгоритм очереди без блокировок на основе связного списка

9 Основные идеи 2. Развернутый связный список Вместо одиночных элементов – массивы

10 Основные идеи 3. Tsigas, Zhang, 2001 Простой подход к реализации очереди на массиве

11 Новый алгоритм очереди Структура:

12 Новый алгоритм очереди Преимущества: Отсутствие блокировок Использование массивов –Экономия памяти –Эффективность работы с кешом Относительная простота Высокая эффективность

13 Новый алгоритм очереди Недостатки: Алгоритм чуть сложнее, чем у Майкла и Скотта Свойство нечувствительности к параметрам кеша достигается только при выполнении дополнительных условий

14 Сравнение производительности Intel Core 2 Duo

15 Сравнение производительности Sun Microsystems UltraSPARC-T1

16 Спасибо за внимание!