NDLI: A SIMD tabu search implementation for solving the quadratic assignment problem with GPU acceleration

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

Paleoscape model of coastal South Africa during modern human origins: progress in scaling and coupling climate, vegetation, and agent-based models on XSEDE

Extending access to HPC skills through a blended online course

Overview of XSEDE-PRACE collaborative projects in 2014

Bring the NLACE model online using XSEDE and HUBzero

Cyberinfrastructure resources enabling creation of the loblolly pine reference transcriptome

Connecting the non-traditional user-community to the national CyberInfrastructure

Publishing and consuming GLUE v2.0 resource information in XSEDE

GeoHashViz: interactive analytics for mapping spatiotemporal diffusion of Twitter hashtags

NCBI-BLAST programs optimization on XSEDE resources for sustainable aquaculture

ISLET: an isolated, scalable, & lightweight environment for training

Market-based on demand scheduling (MBoDS) in co-operative grid environment

Autotuning OpenACC work distribution via direct search

FlowGate: towards extensible and scalable web-based flow cytometry data analysis

Science gateways for humanities, arts, and social science

A prototype sampling interface for PAPI

The CIPRES workbench: a flexible framework for creating science gateways

A scalable computational approach to political redistricting optimization

On fostering a culture of research cyberinfrastructure grant proposals within a community of service providers in an EPSCoR state

Optimizing codes on the Xeon Phi: a case-study with LAMMPS

Porting scientific libraries to PGAS in XSEDE resources: practice and experience

Discovering the influence of socioeconomic factors on online game behaviors

Incorporating interactive compute environments into web-based training materials using the Cornell job runner service

Jetstream: a self-provisioned, scalable science and engineering cloud environment

Enabling HPC simulation workflows for complex industrial flow problems

Performance examinations of multiple time-stepping algorithms on stampede supercomputer

TAS view of XSEDE users and usage

Bridges: a uniquely flexible HPC resource for new communities and data analytics

A performance predictor for UltraScan supercomputer calculations

Performance assessment of real-time estimation of continuous-time stochastic volatility of financial data on GPUs

Multidisciplinary research and education with open tools: metagenomic analysis of 16S rRNA using Arduino, Android, Mothur and XSEDE

Using data science to understand tape-based archive workloads

CDD: computational discovery desktop

Grouping game players using parallelized k-means on supercomputers

Storage utilization in the long tail of science

Leveraging DiaGrid hub for interactively generating and running parallel programs

The VAT: enhanced video analysis

Advanced user environment design and implementation on integrated multi-architecture supercomputers

Inversion of magnetotelluric data using integral equation approach with variable sensitivity domain: application to earthscope MT data

Integrating apache spark into PBS-Based HPC environments

A SIMD tabu search implementation for solving the quadratic assignment problem with GPU acceleration

Content Provider	ACM Digital Library
Author	Qasem, Apan Novoa, Clara Chaparala, Abhilash
Abstract	In the Quadratic Assignment Problem (QAP), n units (usually departments, machines, or electronic components) must be assigned to n locations given the distance between the locations and the flow between the units. The goal is to find the assignment that minimizes the sum of the products of distance traveled and flow between units. The QAP is a combinatorial problem difficult to solve to optimality even for problems where n is relatively small (e.g., n = 30). In this paper, we develop a parallel tabu search algorithm to solve the QAP and leverage the compute capabilities of current GPUs. The single instruction multiple data (SIMD) algorithm is implemented on the Stampede cluster hosted by the Texas Advanced Computing Center (TACC) at the University of Texas at Austin. We enhance our implementation by exploiting the dynamic parallelism made available in the Nvidia Kepler high performance computing architecture. On a series of experiments on the well-known QAPLIB data sets, our algorithm produces solutions that are as good as the best known ones posted in QAPLIB. The worst case percentage of accuracy we obtained was 0.83%. Given the applicability of QAP, our algorithm has very good potential to accelerate scholarly research in Engineering, in the fields of Operations Research and design of electronic devices. To the best of our knowledge, this work is the first to successfully parallelize the tabu search metaheuristic to solve the QAP with the recency-based feature, implemented serially in [10]. Our work is also the first to exploit GPU dynamic parallelism in a tabu search metaheuristic to solve the QAP.
Starting Page	1
Ending Page	8
Page Count	8
File Format	PDF
ISBN	9781450337205
DOI	10.1145/2792745.2792758
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2015-07-26
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Parallel computing Dynamic parallelism Tabu search Gpu computing Quadratic assignment problem
Content Type	Text
Resource Type	Article

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

A SIMD Solution for the Quadratic Assignment Problem with GPU Acceleration

A GPU-based iterated tabu search for solving the quadratic 3-dimensional assignment problem

A GPU-based Iterated Tabu Search for Solving the Quadratic 3-dimensional Assignment Problem

A Parallel Tabu Search for the Large-scale Quadratic Assignment Problem

A Parallel Adaptive Tabu Search Approach (1998)

A GPU-based Iterated Tabu Search for Solving the Quadratic 3-dimensional Assignment Problem

A GPU-based Iterated Tabu Search for Solving the Quadratic 3-dimensional Assignment Problem (2010)

A Parallel Tabu Search Alglorithm for the Quadratic Assignment Problem

The enhanced evolutionary tabu search and its application to the quadratic assignment problem

A SIMD tabu search implementation for solving the quadratic assignment problem with GPU acceleration

Similar Documents

A SIMD Solution for the Quadratic Assignment Problem with GPU Acceleration

A GPU-based iterated tabu search for solving the quadratic 3-dimensional assignment problem

A GPU-based Iterated Tabu Search for Solving the Quadratic 3-dimensional Assignment Problem

A Parallel Tabu Search for the Large-scale Quadratic Assignment Problem

A Parallel Adaptive Tabu Search Approach (1998)

A GPU-based Iterated Tabu Search for Solving the Quadratic 3-dimensional Assignment Problem

A GPU-based Iterated Tabu Search for Solving the Quadratic 3-dimensional Assignment Problem (2010)

A Parallel Tabu Search Alglorithm for the Quadratic Assignment Problem

The enhanced evolutionary tabu search and its application to the quadratic assignment problem

A SIMD tabu search implementation for solving the quadratic assignment problem with GPU acceleration