1 Разработка и анализ параллельных поисковых структур данных, не чувствительных к размеру кеша Акишев Искандер Рустемович Научный руководитель: Елизаров. - презентация

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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