Project BNB-Grid: solving large scale optimization problems in a distributed environment M. Posypkin (ISA RAS) - презентация

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

2 GLOBAL OPTIMIZATION Given f : Find x 0 :

3 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 !

4 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)

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

6 DISTRIBUTED ENVIRONMENT

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

8 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

9 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.

10 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

11 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

12 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:

13 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

14 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

15 THANK YOU!

16

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