A parallel quantum histogram architecture

G. M. Megson, J. O. Cadenas, R. S. Sherratt, P. Huerta, W. C. Kao

Research output: Contribution to journalArticle

Abstract

A parallel formulation of an algorithm for the histogram computation of n data items using an on-the-fly data decomposition and a novel quantum-like representation (QR) is developed. The QR transformation separates multiple data read operations from multiple bin update operations, thereby making it easier to bind data items into their corresponding histogram bins. Under this model, the steps required to compute the histogram is n/s + t steps, where s is a speedup factor, and t is associated with pipeline latency. Here, we show that an overall speedup factor s is available for up to an eightfold acceleration. Our evaluation also shows that each of these cells requires less area/time complexity compared to similar proposals found in the literature.

Original languageEnglish
Article number6508854
Pages (from-to)437-441
Number of pages5
JournalIEEE Transactions on Circuits and Systems II: Express Briefs
Volume60
Issue number7
DOIs
Publication statusPublished - 2013 Apr 30

Fingerprint

Bins
Pipelines
Decomposition

Keywords

  • Histogram
  • parallel algorithms
  • parallel architectures
  • quantum representation

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Cite this

A parallel quantum histogram architecture. / Megson, G. M.; Cadenas, J. O.; Sherratt, R. S.; Huerta, P.; Kao, W. C.

In: IEEE Transactions on Circuits and Systems II: Express Briefs, Vol. 60, No. 7, 6508854, 30.04.2013, p. 437-441.

Research output: Contribution to journalArticle

Megson, G. M. ; Cadenas, J. O. ; Sherratt, R. S. ; Huerta, P. ; Kao, W. C. / A parallel quantum histogram architecture. In: IEEE Transactions on Circuits and Systems II: Express Briefs. 2013 ; Vol. 60, No. 7. pp. 437-441.
@article{b3dcf42ab1ab4e03a446f60e822421d1,
title = "A parallel quantum histogram architecture",
abstract = "A parallel formulation of an algorithm for the histogram computation of n data items using an on-the-fly data decomposition and a novel quantum-like representation (QR) is developed. The QR transformation separates multiple data read operations from multiple bin update operations, thereby making it easier to bind data items into their corresponding histogram bins. Under this model, the steps required to compute the histogram is n/s + t steps, where s is a speedup factor, and t is associated with pipeline latency. Here, we show that an overall speedup factor s is available for up to an eightfold acceleration. Our evaluation also shows that each of these cells requires less area/time complexity compared to similar proposals found in the literature.",
keywords = "Histogram, parallel algorithms, parallel architectures, quantum representation",
author = "Megson, {G. M.} and Cadenas, {J. O.} and Sherratt, {R. S.} and P. Huerta and Kao, {W. C.}",
year = "2013",
month = "4",
day = "30",
doi = "10.1109/TCSII.2013.2258263",
language = "English",
volume = "60",
pages = "437--441",
journal = "IEEE Transactions on Circuits and Systems II: Express Briefs",
issn = "1549-7747",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "7",

}

TY - JOUR

T1 - A parallel quantum histogram architecture

AU - Megson, G. M.

AU - Cadenas, J. O.

AU - Sherratt, R. S.

AU - Huerta, P.

AU - Kao, W. C.

PY - 2013/4/30

Y1 - 2013/4/30

N2 - A parallel formulation of an algorithm for the histogram computation of n data items using an on-the-fly data decomposition and a novel quantum-like representation (QR) is developed. The QR transformation separates multiple data read operations from multiple bin update operations, thereby making it easier to bind data items into their corresponding histogram bins. Under this model, the steps required to compute the histogram is n/s + t steps, where s is a speedup factor, and t is associated with pipeline latency. Here, we show that an overall speedup factor s is available for up to an eightfold acceleration. Our evaluation also shows that each of these cells requires less area/time complexity compared to similar proposals found in the literature.

AB - A parallel formulation of an algorithm for the histogram computation of n data items using an on-the-fly data decomposition and a novel quantum-like representation (QR) is developed. The QR transformation separates multiple data read operations from multiple bin update operations, thereby making it easier to bind data items into their corresponding histogram bins. Under this model, the steps required to compute the histogram is n/s + t steps, where s is a speedup factor, and t is associated with pipeline latency. Here, we show that an overall speedup factor s is available for up to an eightfold acceleration. Our evaluation also shows that each of these cells requires less area/time complexity compared to similar proposals found in the literature.

KW - Histogram

KW - parallel algorithms

KW - parallel architectures

KW - quantum representation

UR - http://www.scopus.com/inward/record.url?scp=84880925167&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84880925167&partnerID=8YFLogxK

U2 - 10.1109/TCSII.2013.2258263

DO - 10.1109/TCSII.2013.2258263

M3 - Article

AN - SCOPUS:84880925167

VL - 60

SP - 437

EP - 441

JO - IEEE Transactions on Circuits and Systems II: Express Briefs

JF - IEEE Transactions on Circuits and Systems II: Express Briefs

SN - 1549-7747

IS - 7

M1 - 6508854

ER -