NDLI: SCC based modulo scheduling for coarse-grained reconfigurable processors

Content Provider	IEEE Xplore Digital Library
Author	Wonsub Kim Donghoon Yoo Haewoo Park Minwook Ahn
Copyright Year	2012
Description	Author affiliation: Samsung Advanced Institute of Technology, Samsung Electronics, San 14, Nongseo-dong, Giheung-gu, Yongin-si, Gyeonggi-do, Korea (Wonsub Kim; Donghoon Yoo; Haewoo Park; Minwook Ahn)
Abstract	Coarse-grained reconfigurable arrays (CGRAs) architectures aim to offer high performance at low power consumption, especially for digital signal processing and streaming applications. To fully exploit the computing capability of CGRA, it is essential to develop a scheduling algorithm which maps operations over processing elements in CGRA. Modulo scheduling [1] is known as the state-of-art algorithm for CGRA scheduling, and there are many variants [2][3][4]. However, they suffer from dealing with inter-iteration dependences called as recurrences that form cyclic dependences. Hence we propose a new scheduling technique that efficiently handles the cyclic dependences. The key techniques are grouping all the mutually-dependent recurrence cycles into a strongly connected component (SCC), and scheduling the input data flow graph (DFG) based on SCCs. Since grouping removes all the recurrence cycles from DFG, the resulting SCC graph becomes a form of directed acyclic graph (DAG) in which the scheduler can track the total order of SCCs. While processing SCCs one by one, our intra-SCC scheduler analyzes the dependences between every pair of two different operations inside of SCC and produces the schedule of them. Thanks to the well-structured form of the SCC-based graph, we obtain more efficient schedule compared to the previous CGRA scheduling algorithm [2]. The experimental results show that the proposed technique enhances the performance of recurrence-dominant loops up to 3.5X and raises the success rate of modulo-scheduling compared to the previous CGRA scheduling algorithm [2].
Starting Page	321
Ending Page	328
File Size	764030
Page Count	8
File Format	PDF
ISBN	9781467328463
e-ISBN	9781467328456
e-ISBN	9781467328449
DOI	10.1109/FPT.2012.6412156
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2012-12-10
Publisher Place	Korea (South)
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Schedules Scheduling Scheduling algorithms Registers Equations Mathematical model Kernel
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

Accurate Constraints Aware Mapping on Coarse-Grained Reconfigurable Architecture

EPIMap: Using Epimorphism to map applications on CGRAs

Thread-Sensitive Modulo Scheduling for Multicore Processors

Branch-aware loop mapping on CGRAs

A scalable scheduling algorithm for coarse-grained reconfigurable architecture

A predicate-aware modulo scheduling for improving resource efficiency of coarse grained reconfigurable architectures

Modulo graph embedding: mapping applications onto coarse-grained reconfigurable architectures

Compiler assisted architectural exploration for coarse grained reconfigurable arrays

Software pipelining for coarse-grained reconfigurable instruction set processors

SCC based modulo scheduling for coarse-grained reconfigurable processors

Similar Documents

Accurate Constraints Aware Mapping on Coarse-Grained Reconfigurable Architecture

EPIMap: Using Epimorphism to map applications on CGRAs

Thread-Sensitive Modulo Scheduling for Multicore Processors

Branch-aware loop mapping on CGRAs

A scalable scheduling algorithm for coarse-grained reconfigurable architecture

A predicate-aware modulo scheduling for improving resource efficiency of coarse grained reconfigurable architectures

Modulo graph embedding: mapping applications onto coarse-grained reconfigurable architectures

Compiler assisted architectural exploration for coarse grained reconfigurable arrays

Software pipelining for coarse-grained reconfigurable instruction set processors

SCC based modulo scheduling for coarse-grained reconfigurable processors