Scalable parallelization strategies to accelerate NuFFT data translation on multicores

Yuanrui Zhang; Jun Liu; Emre Kultursay; Mahmut Kandemir; Nikos Pitsianis; Xiaobai Sun

doi:10.1007/978-3-642-15291-7_13

Scalable parallelization strategies to accelerate NuFFT data translation on multicores

Yuanrui Zhang
, Jun Liu
, Emre Kultursay
, Mahmut Kandemir
, Nikos Pitsianis
, Xiaobai Sun

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

6 Scopus citations

Abstract

The non-uniform FFT (NuFFT) has been widely used in many applications. In this paper, we propose two new scalable parallelization strategies to accelerate the data translation step of the NuFFT on multicore machines. Both schemes employ geometric tiling and binning to exploit data locality, and use recursive partitioning and scheduling with dynamic task allocation to achieve load balancing. The experimental results collected from a commercial multicore machine show that, with the help of our parallelization strategies, the data translation step is no longer the bottleneck in the NuFFT computation, even for large data set sizes, with any input sample distribution.

Original language	English (US)
Title of host publication	Euro-Par 2010 Parallel Processing - 16th International Euro-Par Conference, Proceedings
Pages	125-136
Number of pages	12
Edition	PART 2
DOIs	https://doi.org/10.1007/978-3-642-15291-7_13
State	Published - 2010
Event	16th International Euro-Par Conference on Parallel Processing, Euro-Par 2010 - Ischia, Italy Duration: Aug 31 2010 → Sep 3 2010

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	PART 2
Volume	6272 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	16th International Euro-Par Conference on Parallel Processing, Euro-Par 2010
Country/Territory	Italy
City	Ischia
Period	8/31/10 → 9/3/10

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-15291-7_13

Cite this

Zhang, Y., Liu, J., Kultursay, E., Kandemir, M., Pitsianis, N., & Sun, X. (2010). Scalable parallelization strategies to accelerate NuFFT data translation on multicores. In Euro-Par 2010 Parallel Processing - 16th International Euro-Par Conference, Proceedings (PART 2 ed., pp. 125-136). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6272 LNCS, No. PART 2). https://doi.org/10.1007/978-3-642-15291-7_13

Zhang, Yuanrui ; Liu, Jun ; Kultursay, Emre et al. / Scalable parallelization strategies to accelerate NuFFT data translation on multicores. Euro-Par 2010 Parallel Processing - 16th International Euro-Par Conference, Proceedings. PART 2. ed. 2010. pp. 125-136 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 2).

@inproceedings{13b5d0b117d948898936fbd72f94fb6c,

title = "Scalable parallelization strategies to accelerate NuFFT data translation on multicores",

abstract = "The non-uniform FFT (NuFFT) has been widely used in many applications. In this paper, we propose two new scalable parallelization strategies to accelerate the data translation step of the NuFFT on multicore machines. Both schemes employ geometric tiling and binning to exploit data locality, and use recursive partitioning and scheduling with dynamic task allocation to achieve load balancing. The experimental results collected from a commercial multicore machine show that, with the help of our parallelization strategies, the data translation step is no longer the bottleneck in the NuFFT computation, even for large data set sizes, with any input sample distribution.",

author = "Yuanrui Zhang and Jun Liu and Emre Kultursay and Mahmut Kandemir and Nikos Pitsianis and Xiaobai Sun",

note = "Funding Information: This research is supported in part by NSF grants CNS 0720645, CCF 0811687, OCI 821527, CCF 0702519, CNS 0720749, and a grant from Microsoft.; 16th International Euro-Par Conference on Parallel Processing, Euro-Par 2010 ; Conference date: 31-08-2010 Through 03-09-2010",

year = "2010",

doi = "10.1007/978-3-642-15291-7\_13",

language = "English (US)",

isbn = "3642152902",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

number = "PART 2",

pages = "125--136",

booktitle = "Euro-Par 2010 Parallel Processing - 16th International Euro-Par Conference, Proceedings",

edition = "PART 2",

}

Zhang, Y, Liu, J, Kultursay, E, Kandemir, M, Pitsianis, N & Sun, X 2010, Scalable parallelization strategies to accelerate NuFFT data translation on multicores. in Euro-Par 2010 Parallel Processing - 16th International Euro-Par Conference, Proceedings. PART 2 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 2, vol. 6272 LNCS, pp. 125-136, 16th International Euro-Par Conference on Parallel Processing, Euro-Par 2010, Ischia, Italy, 8/31/10. https://doi.org/10.1007/978-3-642-15291-7_13

Scalable parallelization strategies to accelerate NuFFT data translation on multicores. / Zhang, Yuanrui; Liu, Jun; Kultursay, Emre et al.
Euro-Par 2010 Parallel Processing - 16th International Euro-Par Conference, Proceedings. PART 2. ed. 2010. p. 125-136 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6272 LNCS, No. PART 2).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Scalable parallelization strategies to accelerate NuFFT data translation on multicores

AU - Zhang, Yuanrui

AU - Liu, Jun

AU - Kultursay, Emre

AU - Kandemir, Mahmut

AU - Pitsianis, Nikos

AU - Sun, Xiaobai

N1 - Funding Information: This research is supported in part by NSF grants CNS 0720645, CCF 0811687, OCI 821527, CCF 0702519, CNS 0720749, and a grant from Microsoft.

PY - 2010

Y1 - 2010

N2 - The non-uniform FFT (NuFFT) has been widely used in many applications. In this paper, we propose two new scalable parallelization strategies to accelerate the data translation step of the NuFFT on multicore machines. Both schemes employ geometric tiling and binning to exploit data locality, and use recursive partitioning and scheduling with dynamic task allocation to achieve load balancing. The experimental results collected from a commercial multicore machine show that, with the help of our parallelization strategies, the data translation step is no longer the bottleneck in the NuFFT computation, even for large data set sizes, with any input sample distribution.

AB - The non-uniform FFT (NuFFT) has been widely used in many applications. In this paper, we propose two new scalable parallelization strategies to accelerate the data translation step of the NuFFT on multicore machines. Both schemes employ geometric tiling and binning to exploit data locality, and use recursive partitioning and scheduling with dynamic task allocation to achieve load balancing. The experimental results collected from a commercial multicore machine show that, with the help of our parallelization strategies, the data translation step is no longer the bottleneck in the NuFFT computation, even for large data set sizes, with any input sample distribution.

UR - https://www.scopus.com/pages/publications/78249265973

UR - https://www.scopus.com/pages/publications/78249265973#tab=citedBy

U2 - 10.1007/978-3-642-15291-7_13

DO - 10.1007/978-3-642-15291-7_13

M3 - Conference contribution

AN - SCOPUS:78249265973

SN - 3642152902

SN - 9783642152900

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 125

EP - 136

BT - Euro-Par 2010 Parallel Processing - 16th International Euro-Par Conference, Proceedings

T2 - 16th International Euro-Par Conference on Parallel Processing, Euro-Par 2010

Y2 - 31 August 2010 through 3 September 2010

ER -

Zhang Y, Liu J, Kultursay E, Kandemir M, Pitsianis N, Sun X. Scalable parallelization strategies to accelerate NuFFT data translation on multicores. In Euro-Par 2010 Parallel Processing - 16th International Euro-Par Conference, Proceedings. PART 2 ed. 2010. p. 125-136. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 2). doi: 10.1007/978-3-642-15291-7_13

Scalable parallelization strategies to accelerate NuFFT data translation on multicores

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this