Все выпуски

Рассматривается процедура встраивания оптимизируемых фрагментов маршрутных решений в глобальные решения «большой» задачи, определяемые эвристическими алгоритмами. Постановка задачи маршрутизации учитывает некоторые особенности инженерной задачи о последовательной резке деталей, имеющих каждая один внешний и, возможно, несколько внутренних контуров. Последние должны подвергаться резке раньше внешнего, что приводит к большому числу условий предшествования. Данные условия активно используются в интересах снижения сложности вычислений. Тем не менее размерность задачи остается достаточно большой, что, в частности, не позволяет применять «глобальное» динамическое программирование и вынуждает к использованию эвристических алгоритмов (исследуемая задача относится к числу труднорешаемых в традиционном понимании). Поэтому представляет интерес разработка методов коррекции решений, получаемых на основе упомянутых алгоритмов. В настоящей работе такая коррекция реализуется посредством замены фрагментов (упомянутых решений), имеющих умеренную размерность, оптимальными «блоками», конструируемыми на основе динамического программирования с локальными условиями предшествования, которые согласуются с ограничениями исходной «большой» задачи. Предлагаемая замена не ухудшает, а, в типичных случаях, улучшает качество исходного «эвристического» решения, что подтверждается вычислительным экспериментом на многоядерной ПЭВМ.

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

Рассматриваются способы и варианты привязки параллельных процессов и потоков к ядрам, сокетам вычислительных узлов. Приводятся результаты выполнения тестовых примеров на MPI и MPI/OpenMP. Обсуждаются возможности достижения желаемого размещения параллельного приложения на процессорах и ядрах.

Рассматриваются особенности решения систем уравнений метода Галёркина с разрывными функциями на графических процессорах GPU прямым методом и методами подпространств Крылова с различными предобуславливателями. Производительность программной реализации решения систем на GPU сравнивается с аналогичной, полученной на многоядерном процессоре CPU.

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