Shift buffering technique for automatic code synthesis from synchronous dataflow graphs

Hyunok Oh, Nikil Dutt, Soonho Ha

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations

Abstract

This paper proposes a new efficient buffer management technique called shift buffering for automatic code synthesis from synchronous dataflow graphs (SDF). Two previous buffer management methods, linear buffering and modulo (or circular) buffering, assume that samples are queued in the arc buffers in the arrival order and are accessed by moving the buffer indices. But both methods have significant overhead for general multi-rate systems: the linear buffering method requires large size buffers and the modulo buffering method needs run-time overhead of buffer index computation. The proposed shift buffering method shifts samples rather than moving buffer indices. We develop optimal shift buffering algorithms to minimize the number of shifted samples. Our experimental results show that the proposed algorithm saves up to 90% of performance overhead while requiring the same amount of buffer memory as modulo buffering. Considering the sample copy overhead, shift buffering is applicable when memory size is more crucial than performance overhead, and the shifting overhead is less than the modulo addressing overhead. Another advantage of the shift buffering technique is that it supports the library code written with the linear buffering assumption, which is practically more important.

Original languageEnglish
Title of host publicationCODES+ISSS 2005 - International Conference on Hardware/Software Codesign and Systems Synthesis
PublisherAssociation for Computing Machinery (ACM)
Pages51-56
Number of pages6
ISBN (Print)1595931619, 9781595931610
DOIs
StatePublished - 2005 Jan 1
Event3rd IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and Systems Synthesis CODES+ISSS 2005 - Jersey City, NJ, United States
Duration: 2005 Sep 182005 Sep 21

Publication series

NameCODES+ISSS 2005 - International Conference on Hardware/Software Codesign and System Synthesis

Other

Other3rd IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and Systems Synthesis CODES+ISSS 2005
CountryUnited States
CityJersey City, NJ
Period05/09/1805/09/21

Keywords

  • Automatic code synthesis
  • Buffer management
  • Modulo buffering
  • Shift buffering
  • Synchronous dataflow

Fingerprint Dive into the research topics of 'Shift buffering technique for automatic code synthesis from synchronous dataflow graphs'. Together they form a unique fingerprint.

  • Cite this

    Oh, H., Dutt, N., & Ha, S. (2005). Shift buffering technique for automatic code synthesis from synchronous dataflow graphs. In CODES+ISSS 2005 - International Conference on Hardware/Software Codesign and Systems Synthesis (pp. 51-56). (CODES+ISSS 2005 - International Conference on Hardware/Software Codesign and System Synthesis). Association for Computing Machinery (ACM). https://doi.org/10.1145/1084834.1084852