NDLI: An Exact Resource Constrained-Scheduler using Graph Coloring technique

Content Provider	IEEE Xplore Digital Library
Author	Cherroun, H. Feautrier, P.
Copyright Year	2007
Description	Author affiliation: A.T. Univ., Laghouat (Cherroun, H.)
Abstract	Scheduling is an important technique in high-level synthesis to match application computations and hardware resources. Scheduling a whole program is not possible as too many constraints and objectives interact. We decompose high-level scheduling in three steps. Step 1: Coarse-grain scheduling tries to exploit parallelism and locality of the whole program (in particular in loops, possibly imperfectly nested) with a rough view of the target architecture. This produces a sequence of logical steps, each of which contains a pool of macro-tasks (with no loops). Step 2: Fine-grain scheduling refines each logical step by scheduling all its macro-tasks. Between both steps a resource assignation is done by mapping each macro-task independently. We uniformly expressed the data dependences and resource constraints. As most scheduling problems, scheduling tasks under resources constraints to minimize the total duration is NP-complete. Our goal here is to design strategy for reaching optimal solutions in reasonable time. Our algorithmic contribution is an exact branch-and-bound algorithm, where each evaluation is accelerated by both maximal and greedy clique computation. The effectiveness and efficiency of the approach are good, which is illustrated by means of some practical benchmarks.
Starting Page	554
Ending Page	561
File Size	240957
Page Count	8
File Format	PDF
ISBN	1424410304
DOI	10.1109/AICCSA.2007.370936
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2007-05-13
Publisher Place	Jordan
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Processor scheduling High level synthesis Hardware Parallel processing Acceleration Circuits Size measurement Scheduling algorithm Algorithm design and analysis Computer applications
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

An in-place search algorithm for the resource constrained scheduling problem during high-level synthesis

High-level synthesis of multiple-precision circuits independent of data-objects length

An automatic scheduler for real-time vision applications

Scheduling and resource binding for low power

PEWs: a decentralized dynamic scheduler for ILP processing

Architectural tradeoffs in synthesis of pipelined controls

DLS: A scheduling algorithm for high-level synthesis in VHDL

Bit-level scheduling of heterogeneous behavioural specifications

The Owner Share Scheduler for a Distributed System

An Exact Resource Constrained-Scheduler using Graph Coloring technique

Similar Documents

An in-place search algorithm for the resource constrained scheduling problem during high-level synthesis

High-level synthesis of multiple-precision circuits independent of data-objects length

An automatic scheduler for real-time vision applications

Scheduling and resource binding for low power

PEWs: a decentralized dynamic scheduler for ILP processing

Architectural tradeoffs in synthesis of pipelined controls

DLS: A scheduling algorithm for high-level synthesis in VHDL

Bit-level scheduling of heterogeneous behavioural specifications

The Owner Share Scheduler for a Distributed System

An Exact Resource Constrained-Scheduler using Graph Coloring technique