ParallelSort: Tier-0

Итак, результаты стандартных алгоритмов. Heap sort реализован как

template <class RanIt>  // RanIt == Random Iterator
void heapSort (RanIt begin, RanIt end)
{
  std::make_heap (begin, end);
  std::sort_heap (begin, end);
}

В среднем/худшем случае std::stable_sort оказалась лишь немного хуже std::sort. Последняя обычно является «прокаченным» вариантом introsort с выборкой (вероятной) медианы в качестве опорного элемента и переключением на сортировку вставками при обработке небольших диапазонов, и с ней действительно сложно соревноваться. Высокое качество работы std::sort демонстрируют низкие показатели congestion (соответственно, высокий parallelism). У std::stable_sort они существенно хуже и ещё хуже у пирамидальной сортировки, которая из-за частых промахов кэшей упирается в латентность случайного доступа контроллера DRAM.

Далее: tier-1a bitonic, tier-0 VirtualBox.

Реклама

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s

%d такие блоггеры, как: