Streaming Reduction Circuit

Marco Egbertus Theodorus Gerards; Jan Kuper; Andre B.J. Kokkeler; Egbert Molenkamp

doi:10.1109/DSD.2009.141

Streaming Reduction Circuit

Marco Egbertus Theodorus Gerards, Jan Kuper, Andre B.J. Kokkeler, Egbert Molenkamp

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

7 Citations (Scopus)

122 Downloads (Pure)

Abstract

Reduction circuits are used to reduce rows of ﬂoating point values to single values. Binary ﬂoating 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.

Original language	English
Title of host publication	Proceedings of the 12th EUROMICRO Conference on Digital System Design, Architectures, Methods and Tools
Place of Publication	Los Alamitos
Publisher	IEEE
Pages	287-292
Number of pages	6
ISBN (Print)	978-0-7695-3782-5
DOIs	https://doi.org/10.1109/DSD.2009.141
Publication status	Published - 27 Aug 2009
Event	12th EUROMICRO Conference on Digital System Design, DSD 2009: Architectures, Methods and Tools - Conference and Cultural Centre of the University of Patras, Patras, Greece Duration: 27 Aug 2009 → 29 Aug 2009 Conference number: 12 http://www.iuma.ulpgc.es/dsd09/

Publication series

Name
Publisher	IEEE Computer Society Press

Conference

Conference	12th EUROMICRO Conference on Digital System Design, DSD 2009
Abbreviated title	DSD
Country/Territory	Greece
City	Patras
Period	27/08/09 → 29/08/09
Internet address	http://www.iuma.ulpgc.es/dsd09/

Keywords

METIS-265249
EWI-17041
IR-69388

Access to Document

10.1109/DSD.2009.141

GerardsDSD09Accepted author version, 106 KB

Cite this

@inproceedings{1d8063607a044e57a01e93b93cd0e369,

title = "Streaming Reduction Circuit",

abstract = "Reduction circuits are used to reduce rows of ﬂoating point values to single values. Binary ﬂoating 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 ; 12th EUROMICRO Conference on Digital System Design, DSD 2009 : Architectures, Methods and Tools, DSD ; Conference date: 27-08-2009 Through 29-08-2009",

year = "2009",

month = aug,

day = "27",

doi = "10.1109/DSD.2009.141",

language = "English",

isbn = "978-0-7695-3782-5",

publisher = "IEEE",

pages = "287--292",

booktitle = "Proceedings of the 12th EUROMICRO Conference on Digital System Design, Architectures, Methods and Tools",

address = "United States",

url = "http://www.iuma.ulpgc.es/dsd09/",

}

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, Los Alamitos, pp. 287-292, 12th EUROMICRO Conference on Digital System Design, DSD 2009, Patras, Greece, 27/08/09. https://doi.org/10.1109/DSD.2009.141

Streaming Reduction Circuit. / Gerards, Marco Egbertus Theodorus; Kuper, Jan; Kokkeler, Andre B.J. et al.
Proceedings of the 12th EUROMICRO Conference on Digital System Design, Architectures, Methods and Tools. Los Alamitos: IEEE, 2009. p. 287-292 10.1109/DSD.2009.141.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Streaming Reduction Circuit

AU - Gerards, Marco Egbertus Theodorus

AU - Kuper, Jan

AU - Kokkeler, Andre B.J.

AU - Molenkamp, Egbert

N1 - Conference code: 12

PY - 2009/8/27

Y1 - 2009/8/27

N2 - Reduction circuits are used to reduce rows of ﬂoating point values to single values. Binary ﬂoating 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 ﬂoating point values to single values. Binary ﬂoating 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

CY - Los Alamitos

T2 - 12th EUROMICRO Conference on Digital System Design, DSD 2009

Y2 - 27 August 2009 through 29 August 2009

ER -

Streaming Reduction Circuit

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this