NDLI: A hardware architecture for the Branch and Bound Flow-Shop Scheduling algorithm

Content Provider	IEEE Xplore Digital Library
Author	Daouri, M. Escobar, F.A. Xin Chang Valderrama, C.
Copyright Year	2015
Description	Author affiliation: Fac. Polytech., UMONS, Mons, Belgium (Daouri, M.; Escobar, F.A.; Xin Chang; Valderrama, C.)
Abstract	Branch-and-Bound (B&B) algorithms are one of the most employed techniques in optimization problems. Its complexity increases exponentially with problem size and features a challenging dynamic memory management caused by recursive processing. Most solutions focus on parallel branch evaluation in multi-core CPUs or GPUs. To the best of our knowledge, to the date, no works have employed FPGAs to implement the BB technique. In this paper, we propose a mixed hardware-software architecture to solve the Flow-Shop Scheduling Problem (FSP). We use Vivado HLS to construct a simple processing element (PE) for lower bound computation and integrate it with an ARM processor system. A Xilinx ZYNQ-7020 device is used to synthesize 10 PEs and reach an acceleration of about 5× over bare-metal execution on the same platform. In addition, we propose a pseudo-branching technique for higher computation overlapping attaining speed ups of 10.3× for a maximum problem size of 20 jobs in 20 machines.
Starting Page	1
Ending Page	4
File Size	518176
Page Count	4
File Format	PDF
e-ISBN	9781467365765
DOI	10.1109/NORCHIP.2015.7364362
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2015-10-26
Publisher Place	Norway
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Job shop scheduling Ports (Computers) Graphics processing units Computer architecture Hardware Delays Field programmable gate arrays
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

FlexGrip: A soft GPGPU for FPGAs

An enhanced leakage-aware scheduler for dynamically reconfigurable FPGAs

Novel Algorithm Combining Temporal Partitioning and Sharing of Functional Units

Real-time 3DTV system for autostereoscopic displays

Distributed architecture for efficient indoor localization and orientation

Interconnection Network for Tightly Coupled Accelerators Architecture

A Branch and Bound Heuristic for the Flow Shop Problem

Teaching graphics processing and architecture using a hardware prototyping approach

Accurate and flexible flow-based monitoring for high-speed networks

A hardware architecture for the Branch and Bound Flow-Shop Scheduling algorithm

Similar Documents

FlexGrip: A soft GPGPU for FPGAs

An enhanced leakage-aware scheduler for dynamically reconfigurable FPGAs

Novel Algorithm Combining Temporal Partitioning and Sharing of Functional Units

Real-time 3DTV system for autostereoscopic displays

Distributed architecture for efficient indoor localization and orientation

Interconnection Network for Tightly Coupled Accelerators Architecture

A Branch and Bound Heuristic for the Flow Shop Problem

Teaching graphics processing and architecture using a hardware prototyping approach

Accurate and flexible flow-based monitoring for high-speed networks

A hardware architecture for the Branch and Bound Flow-Shop Scheduling algorithm