Разработка высокоэффективных алгоритмов для крупномасштабных задач: различия между версиями

3. Джаджа и Хелман провели эмпирическое исследование операций вычисления префиксов, сортировки и ранжирования списков на симметричных мультипроцессорах. Исследование сортировки (см. [9]) расширяет модель с параллельными дисками Виттера на иерархию внутренней памяти симметричных мультипроцессоров и использует эту новую вычислительную модель для анализа алгоритма сортировки по образцу общего вида, эффективно работающего в разделяемой памяти. При оценке эффективности используются 9 точно определенных эталонных тестов. В число этих тестов входят распределения входных данных, широко используемые для эталонных тестов сортировки (например, ключи, выбираемые равномерным случайным образом), и тесты, разработанные для проверки работы алгоритма в условиях дисбаланса загрузки и конфликтов памяти, а также для обхода определенных проектных решений, основанных на специфических свойствах входных данных (таких как распределение данных, присутствие дублирующихся ключей, предварительно отсортированные входные данные и т. п.).

Все инструменты и техники разработки алгоритмов, созданные в последние годы, применимы к разработке высокоэффективных алгоритмов. Однако многие из этих инструментов требуют дальнейшей доработки. К примеру, техники программирования, обеспечивающие высокую эффективность использования кэша, являются ключом к высокой производительности, однако конкретные пути реализации пока не вполне ясны – главным образом из-за сложных машинно-зависимых проблем, таких как ограниченная ассоциативность, преобразование виртуальных адресов и все более многоуровневые иерархии высокопроизводительных компьютеров. основной вопрос заключается в том, можно ли найти простые модели в качестве основы для разработки алгоритмов. К примеру, в теории алгоритмы без явного задания параметров кэша [ ] эффективны на всех уровнях иерархии памяти, но на практике лишь немногие из них работают хорошо. Или, скажем, профилирование уже выполняемой программы представляет серьезную проблему в последовательной среде (любой инструмент профилирования меняет поведение наблюдаемого процесса), однако эти проблемы меркнут в сравнении с аналогичными проблемами, возникающими в параллельной или распределенной среде (к примеру, для измерения аппаратного ограничения пропускной способности может потребоваться участие оборудования в виде сетевых переключателей или по меньшей мере их перепрограммирование, что, безусловно, изменит их поведение). Разработка эффективных и переносимых алгоритмов для серийно выпускаемых многоядерных и многократноядерных процессоров представляет собой нерешенную проблему.