A new scheduling algorithm for synthesizing the control blocks of control-dominated circuits
Identifieur interne : 001697 ( Istex/Corpus ); précédent : 001696; suivant : 001698A new scheduling algorithm for synthesizing the control blocks of control-dominated circuits
Auteurs : Shih-Hsu Huang ; Yu-Chin Hsu ; Yen-Jen OyangSource :
- Microprocessing and Microprogramming [ 0165-6074 ] ; 1995.
Abstract
This paper describes a new scheduling algorithm for automatic synthesis of the control blocks of control-dominated circuits. The proposed scheduling algorithm is distinctive in its approach to partition a control/data flow graph (CDFG) into an equivalent state transition graph. It works on the CDFG to exploit operation relocation, chaining, duplication, and unification. The optimization goal is to schedule each execution path as fast as possible. Benchmark data shows that this approach achieved better results over the previous ones in terms of the speedup of the circuit and the number of states and transitions.
Url:
DOI: 10.1016/0165-6074(95)00016-H
Links to Exploration step
ISTEX:72BFF193ED1DF24F02FE5DDDADBBA4620ED9E4A0Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title>A new scheduling algorithm for synthesizing the control blocks of control-dominated circuits</title><author><name sortKey="Huang, Shih Hsu" sort="Huang, Shih Hsu" uniqKey="Huang S" first="Shih-Hsu" last="Huang">Shih-Hsu Huang</name><affiliation><mods:affiliation>Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan</mods:affiliation></affiliation></author><author><name sortKey="Hsu, Yu Chin" sort="Hsu, Yu Chin" uniqKey="Hsu Y" first="Yu-Chin" last="Hsu">Yu-Chin Hsu</name><affiliation><mods:affiliation>Department of Computer Science, University of California, Riverside, CA 92521, USA</mods:affiliation></affiliation></author><author><name sortKey="Oyang, Yen Jen" sort="Oyang, Yen Jen" uniqKey="Oyang Y" first="Yen-Jen" last="Oyang">Yen-Jen Oyang</name><affiliation><mods:affiliation>Corresponding author.</mods:affiliation></affiliation><affiliation><mods:affiliation>Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: yjoyang@csie.ntu.edu.tw</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:72BFF193ED1DF24F02FE5DDDADBBA4620ED9E4A0</idno><date when="1995" year="1995">1995</date><idno type="doi">10.1016/0165-6074(95)00016-H</idno><idno type="url">https://api.istex.fr/document/72BFF193ED1DF24F02FE5DDDADBBA4620ED9E4A0/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001697</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a">A new scheduling algorithm for synthesizing the control blocks of control-dominated circuits</title><author><name sortKey="Huang, Shih Hsu" sort="Huang, Shih Hsu" uniqKey="Huang S" first="Shih-Hsu" last="Huang">Shih-Hsu Huang</name><affiliation><mods:affiliation>Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan</mods:affiliation></affiliation></author><author><name sortKey="Hsu, Yu Chin" sort="Hsu, Yu Chin" uniqKey="Hsu Y" first="Yu-Chin" last="Hsu">Yu-Chin Hsu</name><affiliation><mods:affiliation>Department of Computer Science, University of California, Riverside, CA 92521, USA</mods:affiliation></affiliation></author><author><name sortKey="Oyang, Yen Jen" sort="Oyang, Yen Jen" uniqKey="Oyang Y" first="Yen-Jen" last="Oyang">Yen-Jen Oyang</name><affiliation><mods:affiliation>Corresponding author.</mods:affiliation></affiliation><affiliation><mods:affiliation>Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan</mods:affiliation></affiliation><affiliation><mods:affiliation>E-mail: yjoyang@csie.ntu.edu.tw</mods:affiliation></affiliation></author></analytic><monogr></monogr><series><title level="j">Microprocessing and Microprogramming</title><title level="j" type="abbrev">MIMI</title><idno type="ISSN">0165-6074</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="1995">1995</date><biblScope unit="volume">41</biblScope><biblScope unit="issue">7</biblScope><biblScope unit="page" from="501">501</biblScope><biblScope unit="page" to="519">519</biblScope></imprint><idno type="ISSN">0165-6074</idno></series><idno type="istex">72BFF193ED1DF24F02FE5DDDADBBA4620ED9E4A0</idno><idno type="DOI">10.1016/0165-6074(95)00016-H</idno><idno type="PII">0165-6074(95)00016-H</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0165-6074</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">This paper describes a new scheduling algorithm for automatic synthesis of the control blocks of control-dominated circuits. The proposed scheduling algorithm is distinctive in its approach to partition a control/data flow graph (CDFG) into an equivalent state transition graph. It works on the CDFG to exploit operation relocation, chaining, duplication, and unification. The optimization goal is to schedule each execution path as fast as possible. Benchmark data shows that this approach achieved better results over the previous ones in terms of the speedup of the circuit and the number of states and transitions.</div></front></TEI><istex><corpusName>elsevier</corpusName><author><json:item><name>Shih-Hsu Huang</name><affiliations><json:string>Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan</json:string></affiliations></json:item><json:item><name>Yu-Chin Hsu</name><affiliations><json:string>Department of Computer Science, University of California, Riverside, CA 92521, USA</json:string></affiliations></json:item><json:item><name>Yen-Jen Oyang</name><affiliations><json:string>Corresponding author.</json:string><json:string>Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan</json:string><json:string>E-mail: yjoyang@csie.ntu.edu.tw</json:string></affiliations></json:item></author><subject><json:item><lang><json:string>eng</json:string></lang><value>Scheduling</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>High-level synthesis</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Control-dominated circuit synthesis</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Operation chaining</value></json:item><json:item><lang><json:string>eng</json:string></lang><value>Finite state machines</value></json:item></subject><language><json:string>eng</json:string></language><abstract>This paper describes a new scheduling algorithm for automatic synthesis of the control blocks of control-dominated circuits. The proposed scheduling algorithm is distinctive in its approach to partition a control/data flow graph (CDFG) into an equivalent state transition graph. It works on the CDFG to exploit operation relocation, chaining, duplication, and unification. The optimization goal is to schedule each execution path as fast as possible. Benchmark data shows that this approach achieved better results over the previous ones in terms of the speedup of the circuit and the number of states and transitions.</abstract><qualityIndicators><score>6.116</score><pdfVersion>1.2</pdfVersion><pdfPageSize>540 x 648 pts</pdfPageSize><refBibsNative>true</refBibsNative><keywordCount>5</keywordCount><abstractCharCount>618</abstractCharCount><pdfWordCount>7177</pdfWordCount><pdfCharCount>43580</pdfCharCount><pdfPageCount>19</pdfPageCount><abstractWordCount>93</abstractWordCount></qualityIndicators><title>A new scheduling algorithm for synthesizing the control blocks of control-dominated circuits</title><pii><json:string>0165-6074(95)00016-H</json:string></pii><genre><json:string>research-article</json:string></genre><serie><genre></genre><language><json:string>unknown</json:string></language><title>Technical Report</title></serie><host><volume>41</volume><pii><json:string>S0165-6074(00)X0003-8</json:string></pii><pages><last>519</last><first>501</first></pages><issn><json:string>0165-6074</json:string></issn><issue>7</issue><genre><json:string>Journal</json:string></genre><language><json:string>unknown</json:string></language><title>Microprocessing and Microprogramming</title><publicationDate>1995</publicationDate></host><categories><wos><json:string>COMPUTER SCIENCE, HARDWARE & ARCHITECTURE</json:string></wos></categories><publicationDate>1995</publicationDate><copyrightDate>1995</copyrightDate><doi><json:string>10.1016/0165-6074(95)00016-H</json:string></doi><id>72BFF193ED1DF24F02FE5DDDADBBA4620ED9E4A0</id><fulltext><json:item><original>true</original><mimetype>application/pdf</mimetype><extension>pdf</extension><uri>https://api.istex.fr/document/72BFF193ED1DF24F02FE5DDDADBBA4620ED9E4A0/fulltext/pdf</uri></json:item><json:item><original>true</original><mimetype>text/plain</mimetype><extension>txt</extension><uri>https://api.istex.fr/document/72BFF193ED1DF24F02FE5DDDADBBA4620ED9E4A0/fulltext/txt</uri></json:item><json:item><original>false</original><mimetype>application/zip</mimetype><extension>zip</extension><uri>https://api.istex.fr/document/72BFF193ED1DF24F02FE5DDDADBBA4620ED9E4A0/fulltext/zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/document/72BFF193ED1DF24F02FE5DDDADBBA4620ED9E4A0/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a">A new scheduling algorithm for synthesizing the control blocks of control-dominated circuits</title></titleStmt><publicationStmt><authority>ISTEX</authority><publisher>ELSEVIER</publisher><availability><p>ELSEVIER</p></availability><date>1995</date></publicationStmt><notesStmt><note type="content">Section title: Paper</note></notesStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a">A new scheduling algorithm for synthesizing the control blocks of control-dominated circuits</title><author><persName><forename type="first">Shih-Hsu</forename><surname>Huang</surname></persName><affiliation>Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan</affiliation></author><author><persName><forename type="first">Yu-Chin</forename><surname>Hsu</surname></persName><affiliation>Department of Computer Science, University of California, Riverside, CA 92521, USA</affiliation></author><author><persName><forename type="first">Yen-Jen</forename><surname>Oyang</surname></persName><email>yjoyang@csie.ntu.edu.tw</email><affiliation>Corresponding author.</affiliation><affiliation>Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan</affiliation></author></analytic><monogr><title level="j">Microprocessing and Microprogramming</title><title level="j" type="abbrev">MIMI</title><idno type="pISSN">0165-6074</idno><idno type="PII">S0165-6074(00)X0003-8</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="1995"></date><biblScope unit="volume">41</biblScope><biblScope unit="issue">7</biblScope><biblScope unit="page" from="501">501</biblScope><biblScope unit="page" to="519">519</biblScope></imprint></monogr><idno type="istex">72BFF193ED1DF24F02FE5DDDADBBA4620ED9E4A0</idno><idno type="DOI">10.1016/0165-6074(95)00016-H</idno><idno type="PII">0165-6074(95)00016-H</idno></biblStruct></sourceDesc></fileDesc><profileDesc><creation><date>1995</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>This paper describes a new scheduling algorithm for automatic synthesis of the control blocks of control-dominated circuits. The proposed scheduling algorithm is distinctive in its approach to partition a control/data flow graph (CDFG) into an equivalent state transition graph. It works on the CDFG to exploit operation relocation, chaining, duplication, and unification. The optimization goal is to schedule each execution path as fast as possible. Benchmark data shows that this approach achieved better results over the previous ones in terms of the speedup of the circuit and the number of states and transitions.</p></abstract><textClass><keywords scheme="keyword"><list><head>Keywords</head><item><term>Scheduling</term></item><item><term>High-level synthesis</term></item><item><term>Control-dominated circuit synthesis</term></item><item><term>Operation chaining</term></item><item><term>Finite state machines</term></item></list></keywords></textClass></profileDesc><revisionDesc><change when="1995-05-12">Registration</change><change when="1995-03-16">Modified</change><change when="1995">Published</change></revisionDesc></teiHeader></istex:fulltextTEI></fulltext><metadata><istex:metadataXml wicri:clean="Elsevier, elements deleted: tail"><istex:xmlDeclaration>version="1.0" encoding="utf-8"</istex:xmlDeclaration><istex:docType PUBLIC="-//ES//DTD journal article DTD version 4.5.2//EN//XML" URI="art452.dtd" name="istex:docType"></istex:docType><istex:document><converted-article version="4.5.2" docsubtype="fla"><item-info><jid>MIMI</jid><aid>9500016H</aid><ce:pii>0165-6074(95)00016-H</ce:pii><ce:doi>10.1016/0165-6074(95)00016-H</ce:doi><ce:copyright type="unknown" year="1995"></ce:copyright></item-info><head><ce:dochead><ce:textfn>Paper</ce:textfn></ce:dochead><ce:title>A new scheduling algorithm for synthesizing the control blocks of control-dominated circuits</ce:title><ce:author-group><ce:author><ce:given-name>Shih-Hsu</ce:given-name><ce:surname>Huang</ce:surname><ce:cross-ref refid="AFF1"><ce:sup>a</ce:sup></ce:cross-ref></ce:author><ce:author><ce:given-name>Yu-Chin</ce:given-name><ce:surname>Hsu</ce:surname><ce:cross-ref refid="AFF2"><ce:sup>b</ce:sup></ce:cross-ref></ce:author><ce:author><ce:given-name>Yen-Jen</ce:given-name><ce:surname>Oyang</ce:surname><ce:cross-ref refid="COR1"><ce:sup>∗</ce:sup></ce:cross-ref><ce:cross-ref refid="AFF1"><ce:sup>a</ce:sup></ce:cross-ref><ce:e-address>yjoyang@csie.ntu.edu.tw</ce:e-address></ce:author><ce:affiliation id="AFF1"><ce:label>a</ce:label><ce:textfn>Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan</ce:textfn></ce:affiliation><ce:affiliation id="AFF2"><ce:label>b</ce:label><ce:textfn>Department of Computer Science, University of California, Riverside, CA 92521, USA</ce:textfn></ce:affiliation><ce:correspondence id="COR1"><ce:label>∗</ce:label><ce:text>Corresponding author.</ce:text></ce:correspondence></ce:author-group><ce:date-received day="12" month="9" year="1994"></ce:date-received><ce:date-revised day="16" month="3" year="1995"></ce:date-revised><ce:date-accepted day="12" month="5" year="1995"></ce:date-accepted><ce:abstract><ce:section-title>Abstract</ce:section-title><ce:abstract-sec><ce:simple-para>This paper describes a new scheduling algorithm for automatic synthesis of the control blocks of control-dominated circuits. The proposed scheduling algorithm is distinctive in its approach to partition a control/data flow graph (CDFG) into an equivalent state transition graph. It works on the CDFG to exploit operation relocation, chaining, duplication, and unification. The optimization goal is to schedule each execution path as fast as possible. Benchmark data shows that this approach achieved better results over the previous ones in terms of the speedup of the circuit and the number of states and transitions.</ce:simple-para></ce:abstract-sec></ce:abstract><ce:keywords><ce:section-title>Keywords</ce:section-title><ce:keyword><ce:text>Scheduling</ce:text></ce:keyword><ce:keyword><ce:text>High-level synthesis</ce:text></ce:keyword><ce:keyword><ce:text>Control-dominated circuit synthesis</ce:text></ce:keyword><ce:keyword><ce:text>Operation chaining</ce:text></ce:keyword><ce:keyword><ce:text>Finite state machines</ce:text></ce:keyword></ce:keywords></head></converted-article></istex:document></istex:metadataXml><mods version="3.6"><titleInfo><title>A new scheduling algorithm for synthesizing the control blocks of control-dominated circuits</title></titleInfo><titleInfo type="alternative" contentType="CDATA"><title>A new scheduling algorithm for synthesizing the control blocks of control-dominated circuits</title></titleInfo><name type="personal"><namePart type="given">Shih-Hsu</namePart><namePart type="family">Huang</namePart><affiliation>Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Yu-Chin</namePart><namePart type="family">Hsu</namePart><affiliation>Department of Computer Science, University of California, Riverside, CA 92521, USA</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Yen-Jen</namePart><namePart type="family">Oyang</namePart><affiliation>Corresponding author.</affiliation><affiliation>Department of Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan</affiliation><affiliation>E-mail: yjoyang@csie.ntu.edu.tw</affiliation><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre type="research-article" displayLabel="Full-length article"></genre><originInfo><publisher>ELSEVIER</publisher><dateIssued encoding="w3cdtf">1995</dateIssued><dateValid encoding="w3cdtf">1995-05-12</dateValid><dateModified encoding="w3cdtf">1995-03-16</dateModified><copyrightDate encoding="w3cdtf">1995</copyrightDate></originInfo><language><languageTerm type="code" authority="iso639-2b">eng</languageTerm><languageTerm type="code" authority="rfc3066">en</languageTerm></language><physicalDescription><internetMediaType>text/html</internetMediaType></physicalDescription><abstract lang="en">This paper describes a new scheduling algorithm for automatic synthesis of the control blocks of control-dominated circuits. The proposed scheduling algorithm is distinctive in its approach to partition a control/data flow graph (CDFG) into an equivalent state transition graph. It works on the CDFG to exploit operation relocation, chaining, duplication, and unification. The optimization goal is to schedule each execution path as fast as possible. Benchmark data shows that this approach achieved better results over the previous ones in terms of the speedup of the circuit and the number of states and transitions.</abstract><note type="content">Section title: Paper</note><subject><genre>Keywords</genre><topic>Scheduling</topic><topic>High-level synthesis</topic><topic>Control-dominated circuit synthesis</topic><topic>Operation chaining</topic><topic>Finite state machines</topic></subject><relatedItem type="host"><titleInfo><title>Microprocessing and Microprogramming</title></titleInfo><titleInfo type="abbreviated"><title>MIMI</title></titleInfo><genre type="Journal">journal</genre><originInfo><dateIssued encoding="w3cdtf">199511</dateIssued></originInfo><identifier type="ISSN">0165-6074</identifier><identifier type="PII">S0165-6074(00)X0003-8</identifier><part><date>199511</date><detail type="volume"><number>41</number><caption>vol.</caption></detail><detail type="issue"><number>7</number><caption>no.</caption></detail><extent unit="issue pages"><start>443</start><end>522</end></extent><extent unit="pages"><start>501</start><end>519</end></extent></part></relatedItem><identifier type="istex">72BFF193ED1DF24F02FE5DDDADBBA4620ED9E4A0</identifier><identifier type="DOI">10.1016/0165-6074(95)00016-H</identifier><identifier type="PII">0165-6074(95)00016-H</identifier><recordInfo><recordContentSource>ELSEVIER</recordContentSource></recordInfo></mods></metadata><enrichments><istex:catWosTEI uri="https://api.istex.fr/document/72BFF193ED1DF24F02FE5DDDADBBA4620ED9E4A0/enrichments/catWos"><teiHeader><profileDesc><textClass><classCode scheme="WOS">COMPUTER SCIENCE, HARDWARE & ARCHITECTURE</classCode></textClass></profileDesc></teiHeader></istex:catWosTEI></enrichments></istex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Musique/explor/OperaV1/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001697 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 001697 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Musique
|area= OperaV1
|flux= Istex
|étape= Corpus
|type= RBID
|clé= ISTEX:72BFF193ED1DF24F02FE5DDDADBBA4620ED9E4A0
|texte= A new scheduling algorithm for synthesizing the control blocks of control-dominated circuits
}}
| This area was generated with Dilib version V0.6.21. |  |