NDLI: Matrix partitioning on a virtual shared memory parallel machine

Content Provider	IEEE Xplore Digital Library
Author	Charny, B.
Copyright Year	1990
Abstract	The general problem considered in the paper is partitioning of a matrix operation between processors of a parallel system in an optimum load-balanced way without potential memory contention. The considered parallel system is defined by several features the main of which is availability of a virtual shared memory divided into segments. If partitioning of a matrix operation causes parallel access to the same memory segment with writing data to the segment by at least one processor, then contention between processors arises which implies performance degradation. To eliminate such situation, a restriction is imposed on a class of possible partitionings, so that no two processors would write data to the same segment. On the resulting class of contention-free partitionings, a load-balanced optimum partitioning is defined as satisfying independent minimax criteria. The main result of the paper is an algorithm for finding the optimum partitioning by means of analytical solution of respective minimax problems. The paper also discusses implementation and performance issues related to the algorithm, on the basis of experience at Kendall Square Research Corporation, where the partitioning algorithm was used for creating high-performance parallel matrix libraries.
Sponsorship	IEEE Computer Society
Starting Page	343
Ending Page	355
Page Count	13
File Size	1825559
File Format	PDF
ISSN	10459219
Volume Number	7
Issue Number	4
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1996-04-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Parallel machines Partitioning algorithms Minimax techniques Electronic mail Arithmetic Matrix decomposition Availability Writing Degradation Algorithm design and analysis
Content Type	Text
Resource Type	Article
Subject	Signal Processing Computational Theory and Mathematics Hardware and Architecture

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

A compiler optimization algorithm for shared-memory multiprocessors

The Case for Partitioning Virtual Machines on Multicore Architectures

Heuristic algorithms for scheduling iterative task computations on distributed memory machines

HARP: an open architecture for parallel matrix and signal processing

Fast algorithm for computing discrete cosine transform

Algorithmic redistribution methods for block-cyclic decompositions

Benchmarking parallel processing platforms: an applications perspective

Adaptively scheduling parallel loops in distributed shared-memory systems

A survey of recoverable distributed shared virtual memory systems

Matrix partitioning on a virtual shared memory parallel machine

Similar Documents

A compiler optimization algorithm for shared-memory multiprocessors

The Case for Partitioning Virtual Machines on Multicore Architectures

Heuristic algorithms for scheduling iterative task computations on distributed memory machines

HARP: an open architecture for parallel matrix and signal processing

Fast algorithm for computing discrete cosine transform

Algorithmic redistribution methods for block-cyclic decompositions

Benchmarking parallel processing platforms: an applications perspective

Adaptively scheduling parallel loops in distributed shared-memory systems

A survey of recoverable distributed shared virtual memory systems

Matrix partitioning on a virtual shared memory parallel machine