Сверхмасштабируемые по скорости исполнения алгоритмы

Необходимость обрабатывать огромные объёмы данных позволила сформулировать ряд требований для алгоритма кластеризации. Рассмотрим эти требования:
Минимизация итераций обращения к данным;
Ограниченность ресурсов, в частности памяти системы;
Восстанавливаемость алгоритма;
Работа алгоритма с базой данных в режиме однонаправленного курсора.
Выполнение данных условий, в особенности третьего пункта, определяет алгоритм как масштабируемый. Алгоритм называют масштабируемым, если при неизменной емкости оперативной памяти с увеличением числа записей в базе данных время его работы растет линейно.
В последовательных вычислениях алгоритмы хорошо характеризуются с точки зрения количества операций и требований к памяти. При условии наличия достаточного объема памяти время выполнения последовательного алгоритма пропорционально выполняемой работе. В то время как размер проблемы и требования к памяти остаются существенными факторами в параллельных вычислениях, коммуникационные издержки и баланс нагрузки усложняют определение времени параллельного выполнения. Как правило, баланс нагрузки на процессоры уменьшается с размером ансамбля (количеством доступных процессоров), а накладные расходы на связь увеличиваются с размером ансамбля; оба могут значительно снизить производительность. Что еще более важно, это «уменьшение» в балансировке нагрузки и «увеличение» в связи варьируются в зависимости от алгоритмов, машин и комбинаций алгоритм-машина. Они являются функциями размера системного ансамбля и размера задачи. Изначально быстрая параллельная реализация может замедлиться при увеличении размера системы и проблемы. Улучшенный алгоритм может быть лучшим только для данной архитектуры и только в ограниченном диапазоне размеров системы и задачи.
Найти диапазон превосходства по своей сути трудно. Превосходство определяется с точки зрения времени выполнения, в то время как время выполнения устанавливается на заданной параллельной платформе и при заданном размере системы и задачи. Отсутствие механизма оценки производительности для сравнения диапазонов является текущим барьером параллельного / распределенного программирования.
Масштабируемость - это свойство, которое демонстрирует производительность, линейно пропорциональную количеству используемых процессоров. В течение последних нескольких лет, масштабируемость получила интенсивное внимание. В зависимости от того, как определяется и измеряется мощность производительности, были предложены различные показатели масштабируемости [6].
По сравнению со временем выполнения преимуществом масштабируемости является ее «безразмерность»: она зависит только от начального состояния. Масштабируемость имеет различные приложения. Одним из важных применений «безразмерноcти» является прогнозирование производительности, где предварительно измеренные данные производительности собираются, хранятся и используются для прогнозирования будущей производительности.
Время исполнения является конечной мерой интереса на практике

. Прогнозирование производительности должно происходить с точки зрения исполнения. Поскольку время выполнения зависит от размера проблемы и существует множество возможных комбинаций размера проблемы и распределения данных, время выполнения вряд ли будет собираться управляемым способом для прогнозирования производительности. Практическое решение, по-видимому, представляет собой сочетание масштабируемости и времени выполнения, сохраненной производительности с точки зрения масштабируемости и использования предварительно настроенной масштабируемости для прогнозирования производительности с точки зрения времени выполнения. Интеграция масштабируемости в прогнозирование производительности требует глубокого понимания взаимосвязи между масштабируемостью и временем выполнения.
На основе вновь открытых соотношений вводится понятие сравнения диапазонов. В отличие от обычного сравнения времени выполнения, в котором сравнивается производительность на заданной параллельной платформе и при заданном размере системы и задачи, сравнение диапазона сравнивает производительность в широком диапазоне размеров ансамбля и задачи с помощью анализа точек пересечения производительности. Идея сравнения диапазона проста: найти первую точку пересечения производительности выше/ниже. До встречи с первой точкой пересечения в широком диапазоне размеров системы и проблемы быстрая программа будет оставаться быстрой, а медленная - медленной.
Цель высокопроизводительных вычислений - быстрое решение больших задач. Учитывая время выполнения и размер задачи, то, что мы ищем от параллельной обработки - это скорость, которая определяется как работа разделенная на время. Средняя скорость - это достигнутая скорость, деленная на количество используемых процессоров. Средняя скорость - это величина, которая в идеале была бы неизменной с масштабируемым размером системы. Для большого класса процессоров средняя скорость может поддерживаться путем увеличения размера задачи. Необходимое увеличение размера задачи зависит от комбинаций алгоритм-машина. Это изменение обеспечивает количественное измерение для масштабируемости. Пусть W объем работы алгоритма для р процессоров, работающие в машине, и пусть W' есть объем работы алгоритма, когда процессоры p' n используются для поддержания средней скорости. После масштабируемости сверхскоростных [3], масштабируемость от размера системы p до размера системы p' комбинации алгоритм-машина равна
(2.0)
где работа W' определяется ограничением сверхскорости. Формула была дана в [8] для вычисления W'.
(2.1)
где a - средняя скорость, Δ - постоянная вычислительная мощность одного процессора (обратная скорости), а To (W') - издержки параллельной обработки на P процессорах. Когда параллельная деградация существует (т