Полный текст статьи
Печать

В настоящее время существует проблема оптимального распределения данных между вычислителями в многопроцессорных вычислительных системах с SIMD архитектурой.

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

Таким образом, задача оптимального распределения в современных компьютерных системах имеет огромное практическое значение, её решение позволит разделить огромные кластеры задач между несколькими, в некоторых случаях десятками или сотнями, совместными процессорами, а это, в свою очередь, разрешит проблему нехватки временных и вычислительных ресурсов при решении действительно серьёзных физических, медицинских, математических, а так же общенаучных задач.

Для решения данной проблемы могут применяться различные алгоритмы распределения кластеров задач среди множества различных сопроцессоров, которые составляют собой компьютерную систему высокого ранга.

Одним из способов является алгоритм «бустрофедона», который обладает высокой эффективностью распределения, низкими затратами времени, наименьшей погрешностью, а самое главное сложностью всего лишь O(N2).

Сложность алгоритма оценивается, как порядок максимально прорастающей части функции, которой можно выразить количество операций, проводимых вычислителем за время полной работы алгоритма [1]. То есть в алгоритме «бустрофедона» максимально прирастающая часть это два цикла, один из которых является циклом сортировки, что позволяет исключить его, так как в большинстве современных архитектур сортировка выполняется на нижнем уровне работы программы и происходит гораздо быстрее, чем при сортировке на верхних уровнях, то есть при написании этого фрагмента кода алгоритма вручную.

Точным методом решения задачи распределения выступает алгоритм полного перебора. Этот алгоритм занимает наибольшее время и объём памяти, так как использует самый простой в понимании метод решения: перебираем все доступные варианты, а затем выбираем из них наиболее подходящий. То есть данный алгоритм требует хранения всех результатов и последующего попарного сравнения для выявления самого оптимального варианта. Или же хранения одного варианта постоянно, а одного переменного, который сравнивается с постоянным и, если он оказывается лучше, по определённым параметрам, заменяет собой постоянный. Сложность этого алгоритма оценивается как O(2N).

Такая сложность говорит о том, что в данном алгоритме количество операций возрастает экспоненциально, то есть в его структуре присутствует как минимум один вложенный цикл. Причём в этом алгоритме не используется методов, позволяющих опуститься на нижний уровень и ускорить работу, так что с ростом числа элементов распределения, задача распределения становится неразрешимой, в определённые временные рамки.

Другим точным алгоритмом можно считать метод ветвей и границ [4]. Это одна из вариаций полного перебора, за исключением того, что в нём производится отсечение заведомо неоптимальных ветвей дерева, что позволит сократить количество действий и упростить алгоритм. Но этот метод сильно зависит от начальных условий. Его сложность оценить не представляется возможным, ведь в каждом случае она будет меньше, чем O(2N), но насколько, заранее неизвестно.

Среди приближённых методов решения можно назвать «жадный» алгоритм, этот алгоритм учитывает не только равномерность распределения, но и приоритетность задач. То есть задачи будут распределены максимально равномерно, но сначала алгоритм отправит на вычислители самые приоритетные задачи. Это помогает при выполнении нескольких кластеров задач, например в случае, когда от результатов одного из них зависят результаты остальных, но разделить их не представляется возможным. Сложность этого способа можно оценить как O(N log(N)).

Подобная сложность может означать, что в алгоритме присутствует два сложных цикла, один из которых является сортировкой, причём она проводится как можно более оптимально и оценивается как O(log(N)), а простой цикл распределения оценён в O(N). Приблизительно так же оценивается алгоритм «бустрофедона», но он проще, так как не требует дополнительных данных, таких как приоритетность задачи.

Схема полиномиального времени – это группа способов распределения, которые отличаются тем, что постепенно снижают точность распределения, объединяя близкие по объёму задачи в одну группу, что позволяет уменьшить различия и увеличить скорость получения решения. Существует множество различных способов анализа и упрощения задачи, но все они имеют сложность в виде полинома от N и Ɛ-1, где Ɛ - точность объединения.

Следует отдельно выделить генетические алгоритмы [5]. Эти алгоритмы не могут гарантировать нахождение оптимального решения за полиномиальное время, не дают оценку близости к максимально оптимальному, но позволяют найти близкое к идеальному решение, гораздо быстрее других эвристических алгоритмов. Каждая особь соответствует множеству задач, которые необходимо распределить. Информация при таких методах хранится в виде бинарных строк, в которых каждый бит определяет, отправлена ли эта задача на данный вычислитель. Функция приспособленности в данных алгоритмах определяет близость решения к оптимальному. Например, таковой может служить суммарное время работы всех сопроцессоров при конкретном распределении, которое в любом случае стремится к минимальному [3]. После серии смен поколений, в которых скрещиваются лучшие особи с наиболее высокой приспособленностью, эти алгоритмы должны улучшить исходные решения.

Сложность этих алгоритмов оценить не просто, потому как это не один алгоритм, а целая плеяда различных методов решения проблемы распределения. Можно лишь сказать, что они находятся где-то между алгоритмом «бустрофедона» и алгоритмом полного перебора. Конечно, такая оценка более чем поверхностна, но позволяет иметь хоть какое-то представление об их сложности. Для более точной оценки требуются исследования этих алгоритмов отдельно от остальных.

В заключении хотелось бы отметить, что задача оптимального распределения – это одна из важнейших областей размышлений уже нескольких поколений программистов, каждое из них приносит всё новые и новые идеи и методы решения. Каждый, кто хоть раз задумывался над данной проблемой, приходит к всё более и более интересным результатам. Эдсгер Дейкстра говорил: «Глубоко ошибается тот, кто думает, что изделиями программистов являются программы, которые они пишут. Программист обязан создавать заслуживающие доверия решения и представлять их в форме убедительных доводов, а текст написанной программы является лишь сопроводительным материалом, к которому эти доказательства применимы»[2], он как нельзя более точно описал ситуацию, которая сложилась вокруг программистов, за годы их непрерывной работы для совершенствования алгоритмов решения различного рода прикладных задач, ведь программирование – это самая передовая отрасль прикладной математики. Как изложено выше способов решения очень много, а среди них можно выделить те, которые соответствуют определённым требованиям, которые разнятся в зависимости от конкретных особенностей задачи. Оценка сложности работы алгоритмов позволяют отобрать из них более быстрые и эффективные. Среди перечисленных особо эффективными являются алгоритм «бустрофедона» и, так называемый, «жадный» алгоритм. У этих методов сложность наименьшая, и приблизительно равная, и они отвечают особым условиям, которые могут быть выставлены при постановке задачи. «Бустрофедон» – это просто самый оптимальный из доступных алгоритмов, так как распределяет с наименьшим разбросом и с наибольшей скоростью. «Жадный» алгоритм – это особый метод решения задачи, который даёт возможность выполнить особое распределение, учитывая приоритет задач.

Из чего следует что, задача оптимального распределения имеет множество решений, и новые решения постоянно появляются, что свидетельствует о развитии самой современной отрасли прикладной математики.