NDLI: Out-of-core distribution sort in the FG programming environment

Content Provider	IEEE Xplore Digital Library
Author	Natarajan, P. Cormen, T.H. Strange, E.R.
Copyright Year	2010
Description	Author affiliation: Dartmouth College, Department of Computer Science, USA (Natarajan, P.; Cormen, T.H.) \|\| A9.com, USA (Strange, E.R.)
Abstract	We describe the implementation of an out-of-core, distribution-based sorting program on a cluster using FG, a multithreaded programming framework. FG mitigates latency from disk-I/O and interprocessor communication by overlapping such high-latency operations with other operations. It does so by constructing and executing a coarse-grained software pipeline on each node of the cluster, where each stage of the pipeline runs in its own thread. The sorting program distributes data among the nodes to create sorted runs, and then it merges sorted runs on each node. When distributing data, the rates at which a node sends and receives data will differ. When merging sorted runs, each node will consume data from each of its sorted runs at varying rates. Under these conditions, a single pipeline running on each node is unwieldy to program and not necessarily efficient.We describe how we have extended FG to support multiple pipelines on each node in two forms. When a node might send and receive data at different rates during interprocessor communication, we use disjoint pipelines on each node: one pipeline to send and one pipeline to receive. When a node consumes and produces data from different streams on the node, we use multiple pipelines that intersect at a particular stage. Experimental results show that by using multiple pipelines, an out-of-core, distribution-based sorting program outperforms an out-of-core sorting program based on columnsort-taking approximately 75%–85% of the time-despite the advantages that the columnsort-based program holds.
Starting Page	1
Ending Page	8
File Size	324718
Page Count	8
File Format	PDF
ISBN	9781424465330
e-ISBN	9781424465347
DOI	10.1109/IPDPSW.2010.5470692
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2010-04-19
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Computer science FG Pipelines Merging Clustering algorithms Out-of-core sorting Partitioning algorithms Delay Programming environments Sorting Multithreaded programming framework Latency
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Out-of-core distribution sort in the fg programming environment.

A multithreaded multimedia processor merging on-chip multiprocessors and distributed vector pipelines

The effect of local sort on parallel sorting algorithms

Multithreaded Clustering for Multi-level Hypergraph Partitioning

A clustering algorithm using evolutionary programming

A Parallel Memory Efficient Framework for Out-of-Core Mesh Simplification

CUZ: An Improved Clustering Algorithm

Designing Scalable Out-of-core Sorting with Hybrid MPI+PGAS Programming Models

A new efficient radix sort

Out-of-core distribution sort in the FG programming environment

Similar Documents

Out-of-core distribution sort in the fg programming environment.

A multithreaded multimedia processor merging on-chip multiprocessors and distributed vector pipelines

The effect of local sort on parallel sorting algorithms

Multithreaded Clustering for Multi-level Hypergraph Partitioning

A clustering algorithm using evolutionary programming

A Parallel Memory Efficient Framework for Out-of-Core Mesh Simplification

CUZ: An Improved Clustering Algorithm

Designing Scalable Out-of-core Sorting with Hybrid MPI+PGAS Programming Models

A new efficient radix sort

Out-of-core distribution sort in the FG programming environment