NDLI: Efficient selection algorithms on distributed memory computers

Please wait, while we are loading the content...

PDS/PIO: lightweight libraries for collective parallel I/O

Multi-processor performance on the Tera MTA

An initial evaluation of the Tera Multithreaded Architecture and programming system using the C3I parallel benchmark suite

High Performance Simulation of Internal Combustion Engines

A parallel linear algebra server for Matlab-like environments

Multilevel algorithms for multi-constraint graph partitioning

Pthreads for dynamic and irregular parallelism

Communication overlap in multi-tier parallel algorithms

Making sparse Gaussian elimination scalable by static pivoting

The large scale parallelization of a conformational 3D Protein structure prediction application

Real-time image segmentation for image-guided surgery

Highly efficient gang scheduling implementation

The Penn State computing condominium scheduling system

A grid-enabled MPI: message passing in heterogeneous distributed computing systems

Measurement of a scientific workload using the IBM hardware performance monitor

An infrastructure for efficient parallel job execution in Terascale computing environments

QCDSP machines: design, performance and cost

Scientific visualization in the classroom

Modeling orbiting and rotating bodies using VRML

High performance first principles method for complex magnetic properties

A hierarchical load-balancing framework for dynamic multithreaded computations

The UCLA AGCM in high performance computing environments

Adaptive parallel computation of a grand-challenge problem: prediction of the path of a solar-corona mass ejection

Efficient selection algorithms on distributed memory computers

Optimizing software cache-coherent cluster architectures

StarT-Voyager: a flexible platform for exploring scalable SMP issues

Reducing coherence overhead of barrier synchronization in software DSMs

A new Lanczos method for electronic structure calculations

Linger Longer: fine-grain cycle stealing for networks of workstations

Scaling of Beowulf-class distributed systems

Application of a high performance parallel eigensolver to electronic structure calculations

Synchronous learning at a distance: experiences with Tango

New directions for computational science and supercomputing in secondary school

Internet based audiovisual communication tools used in a joint engineering design class at the University of Alabama in Huntsville and the Ecole Superieure et de Construction Automobile (ESTACA) in Paris, France

A proposal for preservice student technology competence

A virtual university as a distributed computing network

Avalon: an Alpha/Linux cluster achieves 10 Gflops for \$15k

A case for using MPI's derived datatypes to improve I/O performance

Techniques for speculative run-time parallelization of loops

An implementation and analysis of the virtual interface architecture

MPI-StarT: delivering network performance to numerical applications

High performance multidimensional analysis and data mining

A prototype notebook-based environment for computational tools

Dynamic repartitioning of adaptively refined meshes

Supporting runtime tool interaction for parallel simulations

Automatically tuned linear algebra software

An out-of-core implementation of the COLUMBUS massively-parallel multireference configuration interaction program

A parallel rendezvous algorithm for interpolation between multiple grids

3D in the Pines and on the Plains

Secondary Science & Mathematics Teachers Communicating Using Collaborative Tools via Distance Learning Technology: hands-on session

Building the infrastructure for high performance computing in undergraduate curricula: ten Grand Challenges and the response of the NPACI education center

TFLOPS PFS: architecture and design of a highly efficient parallel file system

Efficient algorithms for block-cyclic array redistribution between processor sets

High performance Fortran compilation techniques for parallelizing scientific codes

Overture: an object-oriented framework for high performance scientific computing

Agent middleware for heterogeneous scientific simulations

User-space communication: a quantitative study

Analyzing the error bounds of multipole-based treecodes

CCF: Collaborative Computing Frameworks

A collaborative framework for distributed microscopy

S-HARP: a scalable parallel dynamic partitioner for adaptive mesh-based computations

OpenMP on networks of workstations

Tuning Strassen's matrix multiplication for memory efficiency

A scalable and highly available system for serving dynamic data at frequently accessed web sites

WebFlow: high-level programming environment and visual authoring toolkit for high performance distributed computing

Accurate performance evaluation, modelling and prediction of a message passing simulation code based on middleware

The RiverWeb Toolsuite™: bridging the gap between high-end environmental science and the classroom

REU PACI---undergraduate student research experiences

Using high performance GIS software to visualize data: a hands-on software demonstration

A comparison of automatic parallelization tools/compilers on the SGI origin 2000

Training teachers to use information technology to support integrated instruction: what teacher trainers learned from their students

Every picture tells a story: learning to look at space scientific data images

Efficient selection algorithms on distributed memory computers

Content Provider	ACM Digital Library
Author	Song, S. W. Saukas, E. L. G.
Abstract	Consider the selection problem of determining the k th smallest element of a sequence of n elements. Under the CGM (Coarse Grained Multicomputer) model with p processors and O(n/p) local memory, we present a deterministic parallel algorithm for the selection problem that requires O(log p) communication rounds. Besides requiring a low number of communication rounds, the algorithm also attempts to minimize the total amount of data transmitted in each round (only O(p) except in the last round). The basic algorithm is then extended to solve the problem of q simultaneous selections using the same input sequence, also in O(log p) communication rounds and asymptotically same local computing time (if q = O(p) ). The simultaneous selection algorithm gives rise to a communication efficient sorting algorithm, with O(log p) communication rounds and a total of O(p $^{2})$ data transmitted in each round except in the last one. In addition to showing theoretical complexities, we present very promising experimental results obtained on two parallel machines that show almost linear speedup, indicating the efficiency and scalability of the proposed algorithms. To our knowledge, this is the best deterministic CGM algorithm in the literature for the selection problem.
Starting Page	1
Ending Page	26
Page Count	26
File Format	HTM / HTML
ISBN	089791984X
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1998-11-07
Access Restriction	Subscribed
Subject Keyword	Selection problem Parallel algorithm Simultaneous selection Coarse grained multicomputer Sorting
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

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