12-16 April 2010
Uppsala University
Europe/Stockholm timezone

Harnessing Heterogeneous Computing Resources for Solving Hard Computational Problems

Apr 12, 2010, 5:45 PM
Aula (Uppsala University)


Uppsala University

Poster Experiences from application porting and deployment Poster session


Dr Mikhail Posypkin (ISA RAS)


The talk presents the BNB-Grid tool aimed at solving hard combinatorial, discrete and global optimization problems in a distributed heterogeneous computing environment. The BNB-Grid can run applications across different service and desktop grid platforms as well as individual workstations and clusters. The BNB-Grid efficiently copes with difficulties arising in such systems: the software diversity, unreliability of nodes and problems with batch (queuing) system. The talk discusses the implementation details and computational results for two challenging problems.

Detailed analysis

The BNB-Grid tool can harness the consolidated power of computing elements collected from service grids, desktop grids and standalone resources to solve hard optimization and combinatorial problems. Adding new type of computational resource is done in an easy and transparent way via shell scripts incapsulating details of the concrete middleware. Currently the tool supports pure SSH, Unicore and gLite service grids, BOINC and XWHEP desktop grids. The BNB-Grid hypervisor submits applications to different computing elements and organizes their interaction via specially designed protocol. Interaction includes management commands to start and stop computations and exchanging algorithmic information. Two ways of interaction are supported – via TCP/IP sockets and via files where establishing the socket connection is problematic. The BNB-Grid has been successfully applied to molecular conformation problem that plays an important role in computational chemistry and to cryptanalysis of A5/1 cryptosystem. For both problems new results were obtained.


The BNB-Grid tool provides an application-level interoperability among different types of computational resources. The flexible scripting mechanism simplifies adding new resources to the system. Different ways (via TCP/IP or file system) of interaction between the hypervisor and the running application make it possible to easily connect different types of resources. The efficiency of the proposed approach has been demonstrated on two hard optimization problems.

Conclusions and Future Work

In the talk we described the BNB-Grid tool for harnessing heterogeneous computational resources to solve large scale combinatorial and optimization problems. We also discussed the implementation issues of two hard optimization problems from different domains. In future we plan to improve load management part in BNB-Grid and consider new classes of optimization problems.

Keywords Global and Combinatorial Optimization, Application Level Interoperability, Grid Computing
URL for further information http://dcs.isa.ru/posypkin

Primary author

Dr Mikhail Posypkin (ISA RAS)

Presentation materials

There are no materials yet.