NDLI: A parallel backtracking framework (BkFr) for single and multiple clusters

Please wait, while we are loading the content...

javaset: declarative programming in Java with sets

Introduction to NOMADS: networks of mobile adaptive dependable systems

Modeling service-based multimedia content adaptation in pervasive computing

Quantum designer and network simulator

States of matter, information organization and dimensions of expressiveness

Reflections on the memory wall

An active data-aware cache consistency protocol for highly-scalable data-shipping DBMS architectures

Combining compiler and runtime IPC predictions to reduce energy in next generation architectures

Knowledge-based generic intelligent network model

Berserkr: a virtual beowulf cluster for fast prototyping and teaching

Approximating the optimal replacement algorithm

MaRS: a macro-pipelined reconfigurable system

The digital divide of computing

Predictable performance in SMT processors

Accelerating the secure remote password protocol using reconfigurable hardware

A perspective on the future of massively parallel computing: fine-grain vs. coarse-grain parallel models comparison & contrast

Quantum parallelism and the exact simulation of physical systems

Effect of auto-tuning with user's knowledge for numerical software

An architectural framework and a middleware for cooperating smart components

A framework for resource discovery in pervasive computing for mobile aware task execution

Using HDLs for describing quantum circuits: a framework for efficient quantum algorithm simulation

Fighting the memory wall with assisted execution

Reducing traffic generated by conflict misses in caches

A docked-aware storage architecture for mobile computing

An information-interconnectivity-based retrieval method for network attached storage

A parallel backtracking framework (BkFr) for single and multiple clusters

Parallel simulation of orography influence on large-scale atmosphere motion on APEmille

Fault tolerant clockless wave pipeline design

The happy marriage of architecture and application in next-generation reconfigurable systems

Fault secureness need for next generation high performance microprocessor design for testability structures

SoC design of Ogg Vorbis decoder using embedded processor

Opportunities and challenges in application-tuned circuits and architectures based on nanodevices

An architecture to support cooperating mobile embedded systems

Application-level power management in pervasive computing systems: a case study

Toward a quantum process algebra

Biologically inspired rule-based multiset programming paradigm for soft-computing

Self-correcting LRU replacement policies

Improving the execution time of global communication operations

A new technique to calculate dipolar energy and its implementation onto an application specific processor

Reconfigurable platforms for ubiquitous computing

High performance code compression architecture for the embedded ARM/THUMB processor

Model-based evaluation of a radio resource management system for wireless networks

Watson-Crick automata and PCFAS with two components: a computational power analogy

Dynamic techniques to reduce memory traffic in embedded systems

Mobile agent: based module distribution in heterogeneous networks

Repairing return address stack for buffer overflow protection

Physical design methodologies for performance predictability and manufacturability

Integrated temporal and spatial scheduling for extended operand clustered VLIW processors

Overcoming the "Memory Wall" by improved system design exploration and a link to process technology options

Platform-independent methodology for partial reconfiguration

A first glance at Kilo-instruction based multiprocessors

Adaptive architectures for an OTN processor: reducing design costs through reconfigurability and multiprocessing

Designing and testing fault-tolerant techniques for SRAM-based FPGAs

A parallel backtracking framework (BkFr) for single and multiple clusters

Content Provider	ACM Digital Library
Author	Kouril, Michal Paul, Jerome L.
Abstract	There is a wide class of important problems, typified by the NP-complete SAT problem, for which the best known solutions are obtained using the backtracking strategy and heuristics to bound the search of the associated state-space tree. The backtracking strategy is well suited to parallelization, since different portions of the state-space tree can be assigned to different processes. The resulting strategy is often referred to in the literature as parallel depth-first search or parallel backtracking. In this paper we introduce Backtracking Framework (BkFr) that simplifies implementation of the parallel backtracking paradigm in the single cluster environment, and supports the extension of computations over multiple clusters. BkFr uses two communication methods -- MPI for intra-cluster communication and ICI (Inter-Cluster Interface) for inter-cluster communication. What differentiates ICI from MPI-2, Globus and other libraries that support inter-cluster message passing is its lightweight (requiring only Unix socket API and little or no systems administration support), and its fault-tolerant capabilities. The latter capability was one of our principal motivations for developing ICI, since it allows new clusters to join an ongoing computation anytime without affecting the integrity of the whole system. Also, a sudden failure of a cluster that is part of the computation will result in a reassignment of its work to another resource. There are a number of other parallel frameworks for parallel state-space tree searching, such as the ZRAM framework, but they do not support the multi-cluster fault-tolerant option. In addition to its ease of implementation, BkFr offers a simple interface (less than 10 functions) for new compute modules, making it relatively simple for the user to alter existing code to a form suitable for the BkFr framework. To further simplify the utilization of BkFr for solving user-defined problems, we have developed our own Shared Variable Emulation layer, which hides MPI and ICI communication functions, and allows the user to send information (messages) as variables. Because of its lightweight features, our framework does not incur significant additional overhead, and performance data shows good speedup on problems ranging from a simply implemented version of the sum of subsets problem, to complicated implementations of SAT solvers such as SBSAT and zChaff. While the current implementations of ICI and BkFr are developed in the context of MPI, they can readily be adapted to other message passing environments.
Starting Page	302
Ending Page	312
Page Count	11
File Format	PDF
ISBN	1581137419
DOI	10.1145/977091.977134
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2004-04-14
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Backtracking Intra-cluster communication Inter-cluster communication Mpi Sat Ici
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in