Article

PARLGRAN: parallelism granularity selection for scheduling task chains on dynamically reconfigurable architectures

Authors:

Sudarshan Banerjee,

Elaheh Bozorgzadeh,

Nikil DuttAuthors Info & Claims

ASP-DAC '06: Proceedings of the 2006 Asia and South Pacific Design Automation Conference

Pages 491 - 496

https://doi.org/10.1145/1118299.1118419

Published: 24 January 2006 Publication History

Abstract

Partial dynamic reconfiguration, often called RTR (run-time reconfiguration) is a key feature in modern reconfigurable platforms. While partial RTR enables additional application performance, it imposes physical constraints necessitating simultaneous scheduling and placement while mapping application task graphs onto such architectures. In this paper we present PARLGRAN, an approach that maximizes performance of application task chains by selecting a suitable granularity of data-parallelism for individual data parallel tasks. Our approach focusses on reconfiguration delay overhead and placement-related issues (such as fragmentation) while selecting individual data-parallelism granularity as an integral part of simultaneous scheduling and placement. We demonstrate that our heuristic generates high-quality schedules on an extensive set of over a 1000 synthetic experiments by comparing the results with an approach that tries to statically maximize data-parallelism, i.e., does not consider the overheads and constraints associated with partial RTR. A detailed case-study on JPEG encoding additionally confirms that blindly maximizing data-parallelism can result in schedules even worse than that generated by a simple (but RTR-aware) approach oblivious to data-parallelism.

References

[1]

S Banerjee, E Bozorgzadeh, N Dutt, "Physically-aware HW-SW Partitioning for reconfigurable architectures with partial dynamic reconfiguration", DAC, 2005

Digital Library

[2]

J Harkin, T M Mcginnity, L P Maguire, "Modeling and Optimizing Run-Time reconfiguration using evolutionary computation", ACM TECS, V-3, Nov 2004

Digital Library

[3]

P-H Yuh, C-L Yang, Y-W Chang, H-L Chen, "Temporal floorplanning using the T-tree formulation", ICCAD, 2004

Digital Library

[4]

J Noguera, R M Badia, "Power-Performance trade-offs for reconfigurable computing", CODES+ISSS, 2004

Digital Library

[5]

C Steiger, H Walder, M Platzner, "Operating systems for reconfigurable embedded platforms: Online Scheduling of Real-Time Tasks", IEEE Trans on Computers, V-53, 11, Nov 2004

Digital Library

[6]

M Handa, R Vemuri, "An efficient algorithm for finding empty space for online FPGA placement", DAC, 2004

Digital Library

[7]

H Quinn, L A Smith King, M Leeser, W Meleis, "Runtime Assignment of Reconfigurable Hardware Components for Image Processing Pipelines", FCCM, 2003

Digital Library

[8]

S P Fekete, E Kohler, J Teich, "Optimal FPGA module placement with temporal precedence constraints", DATE, 2001

Digital Library

[9]

H Singh, G Lu, E M C Filho, R Maestre, M-H Lee, F J Kurdahi, N Bagherzadeh, "MorphoSys: case study of a reconfigurable computing system targeting multimedia applications", DAC, 2000

Digital Library

[10]

S Hauck, "Configuration pre-fetch for single context reconfigurable processors", FPGA, 1998

Digital Library

[11]

M J Wirthlin, "Improving functional density through Run-time Circuit Reconfiguration", PhD Thesis, Electrical and Computer Engineering Dept, Brigham Young Univesity, 1997

Digital Library

[12]

G Brebner, "A virtual hardware operating system for the Xilinx XC6200", FPL, 1996

Digital Library

[13]

H Murata, K Fujiyoshi, S Nakatake, Y Kajitani, "Rectangle-packing based module placement", ICCAD, 1995

Digital Library

[14]

S Muchnick, "Advanced Compiler design and implementation", Morgan Kaufmann, 1997

Digital Library

[15]

J Augustine, Personal communication

[16]

S Banerjee, E Bozorgzadeh, N Dutt, "Selecting granularity of parallelism for tasks executing on dynamically reconfigurable architectures", CECS Technical Report, UC Irvine.

Cited By

Purgato ATantillo DRabozzi MSciuto DSantambrogio M(2016)Resource-Efficient Scheduling for Partially-Reconfigurable FPGA-Based Systems2016 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)10.1109/IPDPSW.2016.176(189-197)Online publication date: May-2016
https://doi.org/10.1109/IPDPSW.2016.176
Deiana ERabozzi MCattaneo RSantambrogio M(2015)A multiobjective reconfiguration-aware scheduler for FPGA-based heterogeneous architectures2015 International Conference on ReConFigurable Computing and FPGAs (ReConFig)10.1109/ReConFig.2015.7393328(1-6)Online publication date: Dec-2015
https://doi.org/10.1109/ReConFig.2015.7393328
Cattaneo RBellini RDurelli GPilato CSantambrogio MSciuto D(2014)PaRA-SchedProceedings of the 2014 IEEE International Parallel & Distributed Processing Symposium Workshops10.1109/IPDPSW.2014.32(243-250)Online publication date: 19-May-2014
https://dl.acm.org/doi/10.1109/IPDPSW.2014.32
Show More Cited By

Index Terms

Recommendations

Selective bandwidth and resource management in scheduling for dynamically reconfigurable architectures
DAC '07: Proceedings of the 44th annual Design Automation Conference

Partial dynamic reconfiguration (often referred to as partial RTR) enables true on-demand computing. A dynamically invoked application is assigned resources such as data bandwidth, configurable logic, and the limited logic resources are customized ...
Physically-aware HW-SW partitioning for reconfigurable architectures with partial dynamic reconfiguration
DAC '05: Proceedings of the 42nd annual Design Automation Conference

Many reconfigurable architectures offer partial dynamic configurability, but current system-level tools cannot guarantee feasible implementations when exploiting this feature. We present a physically aware hardware-software (HW-SW) scheme for minimizing ...
Integrating physical constraints in HW-SW partitioning for architectures with partial dynamic reconfiguration

Partial dynamic reconfiguration is a key feature of modern reconfigurable architectures such as the Xilinx Virtex series of devices. However, this capability imposes strict placement constraints such that even exact system-level partitioning (and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASP-DAC '06: Proceedings of the 2006 Asia and South Pacific Design Automation Conference

January 2006

998 pages

ISBN:0780394518

General Chair:
Fumiyasu Hirose
Cadence Design Systems, Japan

Sponsors

IEEE Circuits and Systems Society
SIGDA: ACM Special Interest Group on Design Automation
IEICE ESS: Institute of Electronics, Information and Communication Engineers, Engineering Sciences Society
IPSJ SIG-SLDM: Information Processing Society of Japan, SIG System LSI Design Methodology

Publisher

IEEE Press

Publication History

Published: 24 January 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 466 of 1,454 submissions, 32%

Upcoming Conference

ASPDAC '25

Sponsor:
sigda

30th Asia and South Pacific Design Automation Conference

January 20 - 23, 2025

Tokyo , Japan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
274
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Purgato ATantillo DRabozzi MSciuto DSantambrogio M(2016)Resource-Efficient Scheduling for Partially-Reconfigurable FPGA-Based Systems2016 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)10.1109/IPDPSW.2016.176(189-197)Online publication date: May-2016
https://doi.org/10.1109/IPDPSW.2016.176
Deiana ERabozzi MCattaneo RSantambrogio M(2015)A multiobjective reconfiguration-aware scheduler for FPGA-based heterogeneous architectures2015 International Conference on ReConFigurable Computing and FPGAs (ReConFig)10.1109/ReConFig.2015.7393328(1-6)Online publication date: Dec-2015
https://doi.org/10.1109/ReConFig.2015.7393328
Cattaneo RBellini RDurelli GPilato CSantambrogio MSciuto D(2014)PaRA-SchedProceedings of the 2014 IEEE International Parallel & Distributed Processing Symposium Workshops10.1109/IPDPSW.2014.32(243-250)Online publication date: 19-May-2014
https://dl.acm.org/doi/10.1109/IPDPSW.2014.32
Beck ARutzig MCarro L(2014)A transparent and adaptive reconfigurable systemMicroprocessors & Microsystems10.1016/j.micpro.2014.03.00438:5(509-524)Online publication date: 1-Jul-2014
https://dl.acm.org/doi/10.1016/j.micpro.2014.03.004
Banerjee SBozorgzadeh ENoguera JDutt N(2010)Bandwidth Management in Application Mapping for Dynamically Reconfigurable ArchitecturesACM Transactions on Reconfigurable Technology and Systems10.1145/1839480.18394883:3(1-30)Online publication date: 1-Sep-2010
https://dl.acm.org/doi/10.1145/1839480.1839488
Jówiak LNedjah NFigueroa M(2010)Modern development methods and tools for embedded reconfigurable systemsIntegration, the VLSI Journal10.1016/j.vlsi.2009.06.00243:1(1-33)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.1016/j.vlsi.2009.06.002
Hsiung PSantambrogio MHuang C(2009)ReferencesReconfigurable System Design and Verification10.1201/9781420062670.bmatt(225-244)Online publication date: 10-Nov-2009
https://doi.org/10.1201/9781420062670.bmatt
Dragomir OStefanov TBertels K(2009)Optimal Loop Unrolling and Shifting for Reconfigurable ArchitecturesACM Transactions on Reconfigurable Technology and Systems10.1145/1575779.15757852:4(1-24)Online publication date: 1-Sep-2009
https://dl.acm.org/doi/10.1145/1575779.1575785
Santambrogio MRedaelli MMaggioni MLombardi FBhanja SMassoud YBahar R(2009)Task graph scheduling for reconfigurable architectures driven by reconfigurations hiding and resources reuseProceedings of the 19th ACM Great Lakes symposium on VLSI10.1145/1531542.1531552(21-26)Online publication date: 10-May-2009
https://dl.acm.org/doi/10.1145/1531542.1531552
Cordone RRedaelli FRedaelli MSantambrogio MSciuto D(2009)Partitioning and scheduling of task graphs on partially dynamically reconfigurable FPGAsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2009.201573928:5(662-675)Online publication date: 1-May-2009
https://dl.acm.org/doi/10.1109/TCAD.2009.2015739
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents