Project BNB-Grid: solving large scale optimization problems in a distributed environment M. Posypkin (ISA RAS)

GLOBAL OPTIMIZATION Given f : Find x 0 :

APPLICATIONS OF GLOBAL OPTIMIZATION VLSI design Automated theorem proving Constructing optimal transport networks Selecting a best investment package Computational chemistry: finding molecular conformations OFTEN HARD TO SOLVE !

BRANCH-AND-BOUND METHOD BRANCHING TREEBRANCHING SUB-PROBLEM DISCARDED SUBPROBLEM: 1.NO SOLUTION 2.KNOWN OPTIMUM 3.OPTIMUM IS NOT BETTER THAN INCUMBENT (ALREADY FOUND)

BNB parallelization HIGH COMPLEXITY TREE-LIKE STRUCTURE SUITABLE FOR DECOMPOSITION SUITS FOR DISTRIBUTED COMPUTING

DISTRIBUTED ENVIRONMENT

BNB-Grid: ARCHITECTURE CE-AGENT #3 CE-AGENT #1 CE-AGENT #2 MASTER AGENT IARnet

AGENT FUNCTIONALITY Start solver Interact with the CE batch system Load initial data Monitor computing element Send and receive sub-problems Manage distributed application Manage load balancing Monitor and visualize computational process COMPUTING ELEMENT AGENTMASTER AGENT

INSIDE A COMPUTING ELEMENT BNB-Solver BNB-Proxy CE Agent A library for solving optimization problems on multiprocessor and uni-processor systems Interaction with BNB-Solver.

FAULT-TOLERANCE in BNB-Grid Dynamically changing computing space: nodes may leave or join at run-time BNB-Grid backs up sub-problems and resubmits them In the case of the node failure

EXPERIMENTAL RESULTS: PLATFORM МВС BM (JSCC) МВС 6000 IM (CC) Workstation (ISA) 256 x Itanium GHz, 256 GB, Myrinet 1048 x PowerPC 970 2,2 GHz, 2096 GB, Myrinet

EXPERIMENTAL RESULTS: KNAPSACK PROBLEM We are given n items with weights w i and profits p i and a knapsack with capacity C. The objective: select a subset of items such that the total profit is maximized and the total weight does not exceed C:

EXPERIMENTAL RESULTS: DATA The hard knapsack instance (introduced by Finkelshtejn): 8 CPU on MVS BM 5.57 min 8CPU on MVS 6000 IM 6.04 min 8CPU on MVS BM + 8 CPU on MVS 6000 IM 3.15 min

CONCLUSIONS Usage a number of supercomputers in BNB-Grid does increase performance for large scale optimization problems IARnet framework makes development of complex distributed applications rather simple

THANK YOU!

КЛАССИЧЕСКИЕ МОДЕЛЬНЫЕ ЗАДАЧИ ОПТИМИЗАЦИИ Задача коммивояжера Задачи о покрытиях и разрезаниях графов Задача о ранце (одномерная и многомерная) Задачи транспортного типа Поиск глобального экстремума функции многих переменных … ДЛЯ РЕШЕНИЯ ТРЕБУЮТСЯ БОЛЬШИЕ ВЫЧИСЛИТЕЛЬНЫЕ РЕСУРСЫ