<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE article PUBLIC "-//TaxonX//DTD Taxonomic Treatment Publishing DTD v0 20100105//EN" "../../nlm/tax-treatment-NS0.dtd">
<article xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:tp="http://www.plazi.org/taxpub" article-type="research-article" dtd-version="3.0" xml:lang="en">
  <front>
    <journal-meta>
      <journal-id journal-id-type="publisher-id">109</journal-id>
      <journal-id journal-id-type="index">urn:lsid:arphahub.com:pub:3dc5f44e-8666-58db-bc76-a455210e8891</journal-id>
      <journal-title-group>
        <journal-title xml:lang="en">JUCS - Journal of Universal Computer Science</journal-title>
        <abbrev-journal-title xml:lang="en">jucs</abbrev-journal-title>
      </journal-title-group>
      <issn pub-type="ppub">0948-695X</issn>
      <issn pub-type="epub">0948-6968</issn>
      <publisher>
        <publisher-name>Journal of Universal Computer Science</publisher-name>
      </publisher>
    </journal-meta>
    <article-meta>
      <article-id pub-id-type="doi">10.3217/jucs-013-03-0419</article-id>
      <article-id pub-id-type="publisher-id">28758</article-id>
      <article-categories>
        <subj-group subj-group-type="heading">
          <subject>Research Article</subject>
        </subj-group>
        <subj-group subj-group-type="scientific_subject">
          <subject>B.1.2 - Control Structure Performance Analysis and Design Aids</subject>
          <subject>B.5.2 - Design Aids</subject>
          <subject>B.7.2 - Design Aids</subject>
          <subject>C.1.2 - Multiple Data Stream Architectures (Multiprocessors)</subject>
          <subject>C.1.4 - Parallel Architectures</subject>
          <subject>C.5.4 - VLSI Systems</subject>
          <subject>D.3.4 - Processors</subject>
          <subject>Topic A - General Literature</subject>
        </subj-group>
      </article-categories>
      <title-group>
        <article-title>On Pipelining Sequences of Data-Dependent Loops</article-title>
      </title-group>
      <contrib-group content-type="authors">
        <contrib contrib-type="author" corresp="yes">
          <name name-style="western">
            <surname>Rodrigues</surname>
            <given-names>Rui M. M.</given-names>
          </name>
          <email xlink:type="simple">ruirodrigues@gmail.com</email>
          <xref ref-type="aff" rid="A1">1</xref>
        </contrib>
        <contrib contrib-type="author" corresp="no">
          <name name-style="western">
            <surname>Cardoso</surname>
            <given-names>João M. P.</given-names>
          </name>
          <xref ref-type="aff" rid="A1">1</xref>
        </contrib>
      </contrib-group>
      <aff id="A1">
        <label>1</label>
        <addr-line content-type="verbatim">INESC-ID/IST, , Portugal</addr-line>
        <institution>INESC-ID/IST</institution>
        <country>Portugal</country>
      </aff>
      <author-notes>
        <fn fn-type="corresp">
          <p>Corresponding author: Rui M. M. Rodrigues (<email xlink:type="simple">ruirodrigues@gmail.com</email>).</p>
        </fn>
        <fn fn-type="edited-by">
          <p>Academic editor: </p>
        </fn>
      </author-notes>
      <pub-date pub-type="collection">
        <year>2007</year>
      </pub-date>
      <pub-date pub-type="epub">
        <day>28</day>
        <month>03</month>
        <year>2007</year>
      </pub-date>
      <volume>13</volume>
      <issue>3</issue>
      <fpage>419</fpage>
      <lpage>439</lpage>
      <uri content-type="arpha" xlink:href="http://openbiodiv.net/B4EDA110-3246-55CB-9AC4-CBF0C21F2668">B4EDA110-3246-55CB-9AC4-CBF0C21F2668</uri>
      <uri content-type="zenodo_dep_id" xlink:href="https://zenodo.org/record/6999794">6999794</uri>
      <permissions>
        <copyright-statement>Rui M. M. Rodrigues, João M. P. Cardoso</copyright-statement>
        <license license-type="creative-commons-attribution" xlink:href="" xlink:type="simple">
          <license-p>This article is freely available under the J.UCS Open Content License.</license-p>
        </license>
      </permissions>
      <abstract>
        <label>Abstract</label>
        <p>Sequences of data-dependent tasks, each one traversing large data sets, exist in many applications (such as video, image and signal processing applications). Those tasks usually perform computations (with loop intensive behavior) and produce new data to be consumed by subsequent tasks. This paper shows a scheme to pipeline sequences of data-dependent loops, in such a way that subsequent loops can start execution before the completion of the previous ones, which achieves performance improvements. It uses a hardware scheme with decoupled and concurrent data-path and control units that start execution at the same time. The communication of array elements between two loops in sequence is performed by special buffers with a data-driven, fine-grained scheme. Buffer elements are responsible to flag the availability of each array element requested by a subsequent loop (i.e., a ready protocol is used to trigger the execution of operations in the succeeding loop). Thus, the control execution of following loops is also orchestrated by data availability (in this case at the array element grain) and out-of-order produced-consumed pairs are permitted. The concept has been applied using Nau, a compiler infrastructure to map algorithms described in Java onto FPGAs. This paper presents very encouraging results showing important performance improvements and buffer size reductions for a number of benchmarks.</p>
      </abstract>
    </article-meta>
  </front>
</article>
