NDLI: Architecture-Cognizant Divide and Conquer Algorithms

Content Provider	IEEE Xplore Digital Library
Author	Kang Su Gatlin Carter, L.
Copyright Year	1999
Description	Author affiliation: University of California, San Diego (Kang Su Gatlin)
Abstract	Divide and conquer programs can achieve good performance on parallel computers and computers with deep memory hierarchies. We introduce architecture-cognizant divide and conquer algorithms, and explore how they can achieve even better performance. An architecture-cognizant algorithm has functionally-equivalent variants of the divide and/or combine functions, and a variant policy that specifies which variant to use at each level of recursion. An optimal variant policy is chosen for each target computer via experimentation. With h levels of recursion, an exhaustive search requires \theta(vh) experiments (where v is the number of variants). We present a method based on dynamic programming that reduces this to \theta(vc) (where c is typically a small constant) experiments for a class of architecture-cognizant programs. We verify our technique on two kernels (matrix multiply and 2-D Point Jacobi) using three architectures. Our technique improves performance by up to a factor of two, compared to architecture-oblivious divide and conquer implementations. Further our dynamic programming approach succeeds in selecting the optimal variant policy.
Starting Page	25
Ending Page	25
File Size	223588
Page Count	1
File Format	PDF
ISBN	1581130910
DOI	10.1109/SC.1999.10068
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1999-11-13
Access Restriction	Subscribed
Rights Holder	Non IEEE
Subject Keyword	Concurrent computing Dynamic programming Jacobian matrices Computer science Kernel Algorithm design and analysis Read-write memory Parallel programming Random access memory Code standards
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	Mr. Siddhartha Mukherjee siddhartha@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	ndl-support@iitkgp.ac.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Libarray 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

Abstract Architecture-Cognizant Divide and Conquer Algorithms £

Cascading divide-and-conquer: A technique for designing parallel algorithms

Divide-and-conquer-based optimal parallel algorithms for some graph problems on EREW PRAM model

Architecture-Cognizant Divide and Conquer Algorithms (1999)

Architecture-Cognizant Divide and Conquer Algorithms (1999)

Portable High Performance Programming via Architecture-Cognizant Divide-and-Conquer Algorithms (2000)

Parallel external memory graph algorithms

Writing sequential programs for parallel processors: implementation experience

An efficient parallel algorithm for edge-coloring of graphs

Architecture-Cognizant Divide and Conquer Algorithms

Similar Documents

Abstract Architecture-Cognizant Divide and Conquer Algorithms £

Cascading divide-and-conquer: A technique for designing parallel algorithms

Divide-and-conquer-based optimal parallel algorithms for some graph problems on EREW PRAM model

Architecture-Cognizant Divide and Conquer Algorithms (1999)

Architecture-Cognizant Divide and Conquer Algorithms (1999)

Portable High Performance Programming via Architecture-Cognizant Divide-and-Conquer Algorithms (2000)

Parallel external memory graph algorithms

Writing sequential programs for parallel processors: implementation experience

An efficient parallel algorithm for edge-coloring of graphs

Architecture-Cognizant Divide and Conquer Algorithms