• 6 Citations

Abstract

Reduction circuits are used to reduce rows of floating point values to single values. Binary floating point operators often have deep pipelines, which may cause hazards when many consecutive rows have to be reduced. We present an algorithm by which any number of consecutive rows of arbitrary lengths can be reduced by a pipelined commutative and associative binary operator in an efficient manner. The algorithm is simple to implement, has a low latency, produces results in-order, and requires only small buffers. Besides, it uses only a single pipeline for the involved operation. The complexity of the algorithm depends on the depth of the pipeline, not on the length of the input rows. In this paper we discuss an implementation of this algorithm and we prove its correctness.
LanguageUndefined
Title of host publicationProceedings of the 12th EUROMICRO Conference on Digital System Design, Architectures, Methods and Tools
Place of PublicationLos Alamitos
PublisherIEEE Computer Society
Pages287-292
Number of pages6
ISBN (Print)978-0-7695-3782-5
DOIs
StatePublished - 27 Aug 2009
Event12th EUROMICRO Conference on Digital System Design, DSD 2009 - Conference and Cultural Centre of the University of Patras, Patras, Greece
Duration: 27 Aug 200929 Aug 2009
Conference number: 12
http://www.iuma.ulpgc.es/dsd09/

Publication series

Name
PublisherIEEE Computer Society Press

Conference

Conference12th EUROMICRO Conference on Digital System Design, DSD 2009
Abbreviated titleDSD
CountryGreece
CityPatras
Period27/08/0929/08/09
Internet address

Keywords

  • METIS-265249
  • EWI-17041
  • IR-69388

Cite this

Gerards, M. E. T., Kuper, J., Kokkeler, A. B. J., & Molenkamp, E. (2009). Streaming Reduction Circuit. In Proceedings of the 12th EUROMICRO Conference on Digital System Design, Architectures, Methods and Tools (pp. 287-292). [10.1109/DSD.2009.141] Los Alamitos: IEEE Computer Society. DOI: 10.1109/DSD.2009.141
Gerards, Marco Egbertus Theodorus ; Kuper, Jan ; Kokkeler, Andre B.J. ; Molenkamp, Egbert. / Streaming Reduction Circuit. Proceedings of the 12th EUROMICRO Conference on Digital System Design, Architectures, Methods and Tools. Los Alamitos : IEEE Computer Society, 2009. pp. 287-292
@inproceedings{1d8063607a044e57a01e93b93cd0e369,
title = "Streaming Reduction Circuit",
abstract = "Reduction circuits are used to reduce rows of floating point values to single values. Binary floating point operators often have deep pipelines, which may cause hazards when many consecutive rows have to be reduced. We present an algorithm by which any number of consecutive rows of arbitrary lengths can be reduced by a pipelined commutative and associative binary operator in an efficient manner. The algorithm is simple to implement, has a low latency, produces results in-order, and requires only small buffers. Besides, it uses only a single pipeline for the involved operation. The complexity of the algorithm depends on the depth of the pipeline, not on the length of the input rows. In this paper we discuss an implementation of this algorithm and we prove its correctness.",
keywords = "METIS-265249, EWI-17041, IR-69388",
author = "Gerards, {Marco Egbertus Theodorus} and Jan Kuper and Kokkeler, {Andre B.J.} and Egbert Molenkamp",
note = "10.1109/DSD.2009.141",
year = "2009",
month = "8",
day = "27",
doi = "10.1109/DSD.2009.141",
language = "Undefined",
isbn = "978-0-7695-3782-5",
publisher = "IEEE Computer Society",
pages = "287--292",
booktitle = "Proceedings of the 12th EUROMICRO Conference on Digital System Design, Architectures, Methods and Tools",
address = "United States",

}

Gerards, MET, Kuper, J, Kokkeler, ABJ & Molenkamp, E 2009, Streaming Reduction Circuit. in Proceedings of the 12th EUROMICRO Conference on Digital System Design, Architectures, Methods and Tools., 10.1109/DSD.2009.141, IEEE Computer Society, Los Alamitos, pp. 287-292, 12th EUROMICRO Conference on Digital System Design, DSD 2009, Patras, Greece, 27/08/09. DOI: 10.1109/DSD.2009.141

Streaming Reduction Circuit. / Gerards, Marco Egbertus Theodorus; Kuper, Jan; Kokkeler, Andre B.J.; Molenkamp, Egbert.

Proceedings of the 12th EUROMICRO Conference on Digital System Design, Architectures, Methods and Tools. Los Alamitos : IEEE Computer Society, 2009. p. 287-292 10.1109/DSD.2009.141.

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

TY - GEN

T1 - Streaming Reduction Circuit

AU - Gerards,Marco Egbertus Theodorus

AU - Kuper,Jan

AU - Kokkeler,Andre B.J.

AU - Molenkamp,Egbert

N1 - 10.1109/DSD.2009.141

PY - 2009/8/27

Y1 - 2009/8/27

N2 - Reduction circuits are used to reduce rows of floating point values to single values. Binary floating point operators often have deep pipelines, which may cause hazards when many consecutive rows have to be reduced. We present an algorithm by which any number of consecutive rows of arbitrary lengths can be reduced by a pipelined commutative and associative binary operator in an efficient manner. The algorithm is simple to implement, has a low latency, produces results in-order, and requires only small buffers. Besides, it uses only a single pipeline for the involved operation. The complexity of the algorithm depends on the depth of the pipeline, not on the length of the input rows. In this paper we discuss an implementation of this algorithm and we prove its correctness.

AB - Reduction circuits are used to reduce rows of floating point values to single values. Binary floating point operators often have deep pipelines, which may cause hazards when many consecutive rows have to be reduced. We present an algorithm by which any number of consecutive rows of arbitrary lengths can be reduced by a pipelined commutative and associative binary operator in an efficient manner. The algorithm is simple to implement, has a low latency, produces results in-order, and requires only small buffers. Besides, it uses only a single pipeline for the involved operation. The complexity of the algorithm depends on the depth of the pipeline, not on the length of the input rows. In this paper we discuss an implementation of this algorithm and we prove its correctness.

KW - METIS-265249

KW - EWI-17041

KW - IR-69388

U2 - 10.1109/DSD.2009.141

DO - 10.1109/DSD.2009.141

M3 - Conference contribution

SN - 978-0-7695-3782-5

SP - 287

EP - 292

BT - Proceedings of the 12th EUROMICRO Conference on Digital System Design, Architectures, Methods and Tools

PB - IEEE Computer Society

CY - Los Alamitos

ER -

Gerards MET, Kuper J, Kokkeler ABJ, Molenkamp E. Streaming Reduction Circuit. In Proceedings of the 12th EUROMICRO Conference on Digital System Design, Architectures, Methods and Tools. Los Alamitos: IEEE Computer Society. 2009. p. 287-292. 10.1109/DSD.2009.141. Available from, DOI: 10.1109/DSD.2009.141