Meta-Algorithms for Scheduling a Chain of Coarse-Grained Tasks on an Array of Reconfigurable FPGAs

This paper considers the problem of scheduling a chain of n coarse-grained tasks on a linear array of k reconfigurable FPGAs with the objective of primarily minimizing reconfiguration time. A high-level meta-algorithm along with two detailed meta-algorithms (GPRM and SPRM) that support a wide range...

Full description

Saved in:
Bibliographic Details
Published in:VLSI Design 2013-01, Vol.2013 (2013), p.58-70
Main Authors: Mehta, Dinesh P., Bouldin, Donald W., Shetters, Carl
Format: Article
Language:English
Subjects:
Algorithms
Colleges & universities
Computer science
Heuristic
Software
Target recognition
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-a521t-769a8f78f537fa62e96f2557f83e36fe6c6c3c2fd1245dd0bea47a488b6348453
cites cdi_FETCH-LOGICAL-a521t-769a8f78f537fa62e96f2557f83e36fe6c6c3c2fd1245dd0bea47a488b6348453
container_end_page 70
container_issue 2013
container_start_page 58
container_title VLSI Design
container_volume 2013
creator Mehta, Dinesh P.
Bouldin, Donald W.
Shetters, Carl
description This paper considers the problem of scheduling a chain of n coarse-grained tasks on a linear array of k reconfigurable FPGAs with the objective of primarily minimizing reconfiguration time. A high-level meta-algorithm along with two detailed meta-algorithms (GPRM and SPRM) that support a wide range of problem formulations and cost functions is presented. GPRM, the more general of the two schemes, reduces the problem to computing a shortest path in a DAG; SPRM, the less general scheme, employs dynamic programming. Both meta algorithms are linear in n and compute optimal solutions. GPRM can be exponential in k but is nevertheless practical because k is typically a small constant. The deterministic quality of this meta algorithm and the guarantee of optimal solutions for all of the formulations discussed make this approach a powerful alternative to other metatechniques such as simulated annealing and genetic algorithms.
doi_str_mv 10.1155/2013/249592
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_miscellaneous_1506373238</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><airiti_id>P20151222006_201312_201611300032_201611300032_58_70</airiti_id><sourcerecordid>1506373238</sourcerecordid><originalsourceid>FETCH-LOGICAL-a521t-769a8f78f537fa62e96f2557f83e36fe6c6c3c2fd1245dd0bea47a488b6348453</originalsourceid><addsrcrecordid>eNqFkc9LHDEUxwdRqNWeei4Eeikto_md7HFZ6lZRKq2F3sLbmZfd2NmJJjsU_3szHangxdN7j3zyzeOTqnrP6AljSp1yysQplzM143vVIVNa1IoZtl96qlXp5e831ducbyllstw4rFZXuIN63q1jCrvNNhMfE_nZbLAdutCvCZDFBkJPoieLCCljvUxlxpbcQP6TSewJ9GSeEjyMzA9sYu_Dekiw6pCcXS_n-bg68NBlfPdUj6pfZ19vFt_qy-_L88X8sgbF2a42egbWG-uVMB40x5n2XCnjrUChPepGN6LhvmVcqralKwRpQFq70kJaqcRR9WnKvUvxfsC8c9uQG-w66DEO2TFFtTCCC1vQjy_Q2zikvmznRmlG2yKxUF8mqkkx54Te3aWwhfTgGHWjbzf6dpPvQn-e6E3oW_gbXoE_TDAWBD38h6Uygo1PX0znEMq_hOf1rkuKYpxzSvW_RMbHohkTlFLxYlDWGSoeAaljmqM</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>1563768249</pqid></control><display><type>article</type><title>Meta-Algorithms for Scheduling a Chain of Coarse-Grained Tasks on an Array of Reconfigurable FPGAs</title><source>Publicly Available Content (ProQuest)</source><source>Wiley Open Access</source><creator>Mehta, Dinesh P. ; Bouldin, Donald W. ; Shetters, Carl</creator><contributor>Dutt, Shantanu</contributor><creatorcontrib>Mehta, Dinesh P. ; Bouldin, Donald W. ; Shetters, Carl ; Dutt, Shantanu</creatorcontrib><description>This paper considers the problem of scheduling a chain of n coarse-grained tasks on a linear array of k reconfigurable FPGAs with the objective of primarily minimizing reconfiguration time. A high-level meta-algorithm along with two detailed meta-algorithms (GPRM and SPRM) that support a wide range of problem formulations and cost functions is presented. GPRM, the more general of the two schemes, reduces the problem to computing a shortest path in a DAG; SPRM, the less general scheme, employs dynamic programming. Both meta algorithms are linear in n and compute optimal solutions. GPRM can be exponential in k but is nevertheless practical because k is typically a small constant. The deterministic quality of this meta algorithm and the guarantee of optimal solutions for all of the formulations discussed make this approach a powerful alternative to other metatechniques such as simulated annealing and genetic algorithms.</description><identifier>ISSN: 1065-514X</identifier><identifier>EISSN: 1563-5171</identifier><identifier>DOI: 10.1155/2013/249592</identifier><language>eng</language><publisher>Cairo, Egypt: Hindawi Limiteds</publisher><subject>Algorithms ; Colleges &amp; universities ; Computer science ; Heuristic ; Software ; Target recognition</subject><ispartof>VLSI Design, 2013-01, Vol.2013 (2013), p.58-70</ispartof><rights>Copyright © 2013 Dinesh P. Mehta et al.</rights><rights>Copyright © 2013 Dinesh P. Mehta et al. Dinesh P. Mehta et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-a521t-769a8f78f537fa62e96f2557f83e36fe6c6c3c2fd1245dd0bea47a488b6348453</citedby><cites>FETCH-LOGICAL-a521t-769a8f78f537fa62e96f2557f83e36fe6c6c3c2fd1245dd0bea47a488b6348453</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktopdf>$$Uhttps://www.proquest.com/docview/1563768249/fulltextPDF?pq-origsite=primo$$EPDF$$P50$$Gproquest$$Hfree_for_read</linktopdf><linktohtml>$$Uhttps://www.proquest.com/docview/1563768249?pq-origsite=primo$$EHTML$$P50$$Gproquest$$Hfree_for_read</linktohtml><link.rule.ids>314,780,784,25753,27924,27925,37012,37013,44590,74998</link.rule.ids></links><search><contributor>Dutt, Shantanu</contributor><creatorcontrib>Mehta, Dinesh P.</creatorcontrib><creatorcontrib>Bouldin, Donald W.</creatorcontrib><creatorcontrib>Shetters, Carl</creatorcontrib><title>Meta-Algorithms for Scheduling a Chain of Coarse-Grained Tasks on an Array of Reconfigurable FPGAs</title><title>VLSI Design</title><description>This paper considers the problem of scheduling a chain of n coarse-grained tasks on a linear array of k reconfigurable FPGAs with the objective of primarily minimizing reconfiguration time. A high-level meta-algorithm along with two detailed meta-algorithms (GPRM and SPRM) that support a wide range of problem formulations and cost functions is presented. GPRM, the more general of the two schemes, reduces the problem to computing a shortest path in a DAG; SPRM, the less general scheme, employs dynamic programming. Both meta algorithms are linear in n and compute optimal solutions. GPRM can be exponential in k but is nevertheless practical because k is typically a small constant. The deterministic quality of this meta algorithm and the guarantee of optimal solutions for all of the formulations discussed make this approach a powerful alternative to other metatechniques such as simulated annealing and genetic algorithms.</description><subject>Algorithms</subject><subject>Colleges &amp; universities</subject><subject>Computer science</subject><subject>Heuristic</subject><subject>Software</subject><subject>Target recognition</subject><issn>1065-514X</issn><issn>1563-5171</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2013</creationdate><recordtype>article</recordtype><sourceid>PIMPY</sourceid><recordid>eNqFkc9LHDEUxwdRqNWeei4Eeikto_md7HFZ6lZRKq2F3sLbmZfd2NmJJjsU_3szHangxdN7j3zyzeOTqnrP6AljSp1yysQplzM143vVIVNa1IoZtl96qlXp5e831ducbyllstw4rFZXuIN63q1jCrvNNhMfE_nZbLAdutCvCZDFBkJPoieLCCljvUxlxpbcQP6TSewJ9GSeEjyMzA9sYu_Dekiw6pCcXS_n-bg68NBlfPdUj6pfZ19vFt_qy-_L88X8sgbF2a42egbWG-uVMB40x5n2XCnjrUChPepGN6LhvmVcqralKwRpQFq70kJaqcRR9WnKvUvxfsC8c9uQG-w66DEO2TFFtTCCC1vQjy_Q2zikvmznRmlG2yKxUF8mqkkx54Te3aWwhfTgGHWjbzf6dpPvQn-e6E3oW_gbXoE_TDAWBD38h6Uygo1PX0znEMq_hOf1rkuKYpxzSvW_RMbHohkTlFLxYlDWGSoeAaljmqM</recordid><startdate>20130101</startdate><enddate>20130101</enddate><creator>Mehta, Dinesh P.</creator><creator>Bouldin, Donald W.</creator><creator>Shetters, Carl</creator><general>Hindawi Limiteds</general><general>Hindawi Puplishing Corporation</general><general>Hindawi Publishing Corporation</general><general>Hindawi Limited</general><scope>188</scope><scope>ADJCN</scope><scope>AHFXO</scope><scope>RHU</scope><scope>RHW</scope><scope>RHX</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>3V.</scope><scope>7SP</scope><scope>7XB</scope><scope>8AL</scope><scope>8FD</scope><scope>8FE</scope><scope>8FG</scope><scope>8FK</scope><scope>ABUWG</scope><scope>AFKRA</scope><scope>ARAPS</scope><scope>AZQEC</scope><scope>BENPR</scope><scope>BGLVJ</scope><scope>CCPQU</scope><scope>CWDGH</scope><scope>DWQXO</scope><scope>GNUQQ</scope><scope>HCIFZ</scope><scope>JQ2</scope><scope>K7-</scope><scope>L7M</scope><scope>M0N</scope><scope>P5Z</scope><scope>P62</scope><scope>PIMPY</scope><scope>PQEST</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>PRINS</scope><scope>Q9U</scope></search><sort><creationdate>20130101</creationdate><title>Meta-Algorithms for Scheduling a Chain of Coarse-Grained Tasks on an Array of Reconfigurable FPGAs</title><author>Mehta, Dinesh P. ; Bouldin, Donald W. ; Shetters, Carl</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-a521t-769a8f78f537fa62e96f2557f83e36fe6c6c3c2fd1245dd0bea47a488b6348453</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2013</creationdate><topic>Algorithms</topic><topic>Colleges &amp; universities</topic><topic>Computer science</topic><topic>Heuristic</topic><topic>Software</topic><topic>Target recognition</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Mehta, Dinesh P.</creatorcontrib><creatorcontrib>Bouldin, Donald W.</creatorcontrib><creatorcontrib>Shetters, Carl</creatorcontrib><collection>Airiti Library</collection><collection>الدوريات العلمية والإحصائية - e-Marefa Academic and Statistical Periodicals</collection><collection>معرفة - المحتوى العربي الأكاديمي المتكامل - e-Marefa Academic Complete</collection><collection>Hindawi Publishing Complete</collection><collection>Hindawi Publishing Subscription Journals</collection><collection>Hindawi Publishing Open Access Journals</collection><collection>CrossRef</collection><collection>ProQuest Central (Corporate)</collection><collection>Electronics &amp; Communications Abstracts</collection><collection>ProQuest Central (purchase pre-March 2016)</collection><collection>Computing Database (Alumni Edition)</collection><collection>Technology Research Database</collection><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>ProQuest Central (Alumni) (purchase pre-March 2016)</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central</collection><collection>Advanced Technologies &amp; Aerospace Database‎ (1962 - current)</collection><collection>ProQuest Central Essentials</collection><collection>AUTh Library subscriptions: ProQuest Central</collection><collection>Technology Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Middle East &amp; Africa Database</collection><collection>ProQuest Central</collection><collection>ProQuest Central Student</collection><collection>SciTech Premium Collection (Proquest) (PQ_SDU_P3)</collection><collection>ProQuest Computer Science Collection</collection><collection>Computer Science Database</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computing Database</collection><collection>ProQuest Advanced Technologies &amp; Aerospace Database</collection><collection>ProQuest Advanced Technologies &amp; Aerospace Collection</collection><collection>Publicly Available Content (ProQuest)</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>ProQuest Central China</collection><collection>ProQuest Central Basic</collection><jtitle>VLSI Design</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Mehta, Dinesh P.</au><au>Bouldin, Donald W.</au><au>Shetters, Carl</au><au>Dutt, Shantanu</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Meta-Algorithms for Scheduling a Chain of Coarse-Grained Tasks on an Array of Reconfigurable FPGAs</atitle><jtitle>VLSI Design</jtitle><date>2013-01-01</date><risdate>2013</risdate><volume>2013</volume><issue>2013</issue><spage>58</spage><epage>70</epage><pages>58-70</pages><issn>1065-514X</issn><eissn>1563-5171</eissn><abstract>This paper considers the problem of scheduling a chain of n coarse-grained tasks on a linear array of k reconfigurable FPGAs with the objective of primarily minimizing reconfiguration time. A high-level meta-algorithm along with two detailed meta-algorithms (GPRM and SPRM) that support a wide range of problem formulations and cost functions is presented. GPRM, the more general of the two schemes, reduces the problem to computing a shortest path in a DAG; SPRM, the less general scheme, employs dynamic programming. Both meta algorithms are linear in n and compute optimal solutions. GPRM can be exponential in k but is nevertheless practical because k is typically a small constant. The deterministic quality of this meta algorithm and the guarantee of optimal solutions for all of the formulations discussed make this approach a powerful alternative to other metatechniques such as simulated annealing and genetic algorithms.</abstract><cop>Cairo, Egypt</cop><pub>Hindawi Limiteds</pub><doi>10.1155/2013/249592</doi><tpages>13</tpages><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 1065-514X
ispartof VLSI Design, 2013-01, Vol.2013 (2013), p.58-70
issn 1065-514X
1563-5171
language eng
recordid cdi_proquest_miscellaneous_1506373238
source Publicly Available Content (ProQuest); Wiley Open Access
subjects Algorithms
Colleges & universities
Computer science
Heuristic
Software
Target recognition
title Meta-Algorithms for Scheduling a Chain of Coarse-Grained Tasks on an Array of Reconfigurable FPGAs
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-07T23%3A24%3A11IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Meta-Algorithms%20for%20Scheduling%20a%20Chain%20of%20Coarse-Grained%20Tasks%20on%20an%20Array%20of%20Reconfigurable%20FPGAs&rft.jtitle=VLSI%20Design&rft.au=Mehta,%20Dinesh%20P.&rft.date=2013-01-01&rft.volume=2013&rft.issue=2013&rft.spage=58&rft.epage=70&rft.pages=58-70&rft.issn=1065-514X&rft.eissn=1563-5171&rft_id=info:doi/10.1155/2013/249592&rft_dat=%3Cproquest_cross%3E1506373238%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-a521t-769a8f78f537fa62e96f2557f83e36fe6c6c3c2fd1245dd0bea47a488b6348453%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=1563768249&rft_id=info:pmid/&rft_airiti_id=P20151222006_201312_201611300032_201611300032_58_70&rfr_iscdi=true