NDLI: Parallel incremental graph partitioning using linear programming

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

Roundtable session: issues in applying high performance computing to real-time systems

Selecting "best" MPP: do benchmarks really tell the whole story?

Integration of numerical and experimental wind tunnels (IofNEWT)

A scalable high-performance environment for fluid flow analysis on unstructured grids

A high performance parallel algorithm for 1-D FFT

An experimental APL compiler for a distributed memory parallel machine

SLICC: a low latency interface for collective communications

Distributed exploratorium for high performance computational techniques

Towards computations of ocean flows using Navier-Stokes equations

Distributed network computing over local ATM networks

A parallel Gauss-Seidel algorithm for sparse power system matrices

Affinity scheduling of unbalanced workloads

Scalability of the cedar system

Meshes: the next generation

The high performance computing and communications (HPCC) program: technologies for the national information infrastructure

Realizing the benefits of high performance computing for solving environmental and other problems: what do we need beyond faster hardware?

Adaptive data parallel methods for ecosystem monitoring

Nonnumeric search results on the EM-4 distributed-memory multiprocessor

Communication and memory requirements as the basis for mapping task and data parallel programs

Scheduling of unstructured communication on the Intel iPSC/860

Adaptive load migration systems for PVM

Truly distribution-independent algorithms for the N-body problem

Genetic algorithms for graph partitioning and incremental graph partitioning

Architecture of the VPP500 parallel supercomputer

Expressing cross-loop dependencies through hyperplane data dependence analysis

Roundtable discussion: supercomputing support for advanced biomedical imaging

A computational steering model applied to problems in medicine

Orientation determination in the 3D reconstruction of icosahedral viruses using a parallel computer

Applications performance under OSF/1 AD and SUNMOS on Intel Paragon XP/S-15

Using high speed networks to enable distributed parallel image server systems

Dynamic file-access characteristics of a production parallel scientific workload

Tight binding molecular dynamics

Fault-tolerant routing with non-adaptive wormhole algorithms in mesh networks

A portable debugger for parallel and distributed programs

Enabling unimodular transformations

Improved load distribution in parallel sparse cholesky factorization

Findings of the joint NSF-NASA initiative in evaluation

Issues in undergraduate education in computational science and high performance computing

Computer modeling in science education: toward a research and planning agenda

A fixed time performance evaluation of parallel CFD applications

Control strategies for parallel mixed integer branch and bound

A library-based approach to portable, parallel, object-oriented programming: interface, implementation, and application

Run-time and compile-time support for adaptive irregular problems

Are expectations for parallelism too high?: a survey of potential parallel users

Design and implementation of multicast operations for ATM-based high performance computing

Efficient implementation of the multigrid preconditioned conjugate gradient method on distributed memory machines

Non-contiguous processor allocation algorithms for distributed memory multicomputers

Cache performance in vector supercomputers

Performance evaluation: integrating techniques and tools into environments and frameworks

Paramics: moving vehicles on the connection machine

Implementation of a portable and reproducible parallel pseudorandom number generator

Global arrays: a portable "shared-memory" programming model for distributed memory computers

Tolerating node failures in cache only memory architectures

Performance evaluation of three distributed computing environments for scientific applications

GRAPE-4: a one-Tflops special-purpose computer for astrophysical N-body problem

Parallel incremental graph partitioning using linear programming

Sunder: a programmable hardware prefetch architecture for numerical loops

An efficient algorithm for the run-time parallelization of DOACROSS loops

Factors controlling generation and propagation of pacemaker potentials in network models of mammalian SA node

Paging tradeoffs in distributed-shared-memory multiprocessors

Reducing the variance of point to point transfers in the IBM 9076 parallel computer

An efficient abstract interface for multidimensional array I/O

A 65+ Gflop/s unstructured finite element simulation of chemically reacting flows on the Intel Paragon

Optimal software multicast in wormhole-routed multistage networks

The D editor: a new interactive parallel programming tool

Improving the performance of DSM systems via compiler involvement

A scalable parallel algorithm for sparse Cholesky factorization

A parallel iterative linear solver for solving irregular grid semiconductor device matrices

EXTENT: a portable programming environment for designing and implementing high-performance block recursive algorithms

Efficient parallel global garbage collection on massively parallel computers

Building a high-performance collective communication library

The development and operation of edinburgh parallel computing centre's summer scholarship programme

Performance of high-speed network I/O subsystems: case study of a fibre channel network

A parallel formulation of interior point algorithms

Generalized multiprocessor scheduling for directed acylic graphs

The performance of the cedar multistage switching network

A parallel Lauritzen-Spiegelhalter algorithm for probabilistic inference

On the design of Chant: a talking threads package

Application-specific protocols for user-level shared memory

NAS experiences with a prototype cluster of workstations

Scalable parallel formulations of the barnes-hut method for n-body simulations

Efficient communication algorithms for pipeline multicomputers

Efficient and scalable cache coherence schemes for shared memory hypercube multiprocessors

The range test: a dependence test for symbolic, non-linear expressions

Parallel protein structure determination from uncertain data

Parallel performance prediction using lost cycles analysis

Time and/or space sharing in a workstation cluster environment

Dynamic I/O characterization of I/O intensive scientific applications

Applications of boundary element methods on the Intel Paragon

Design and evaluation of a DAMQ multiprocessor network with self-compacting buffers

Interpreting the performance of HPF/Fortran 90D

A compiler-directed cache coherence scheme with improved intertask locality

A high performance linear equation solver on the VPP500 parallel supercomputer

Development and achievement of NAL numerical wind tunnel (NWT) for CFD computations

Parallel incremental graph partitioning using linear programming

Content Provider	ACM Digital Library
Author	Ou, Chao Wei Ranka, Sanjay
Abstract	Partitioning graphs into equally large groups of nodes while minimizing the number of edges between different groups is an extremely important problem in parallel computing. For instance, efficiently parallelizing several scientific and engineering applications requires the partitioning of data or tasks among processors such that the computational load on each node is roughly the same, while communication is minimized. Obtaining exact solutions is computationally intractable, since graph-partitioning is an NP-complete.For a large class of irregular and adaptive data parallel applications (such as adaptive meshes), the computational structure changes from one phase to another in an incremental fashion. In incremental graph-partitioning problems the partitioning of the graph needs to be updated as the graph changes over time; a small number of nodes or edges may be added or deleted at any given instant.In this paper we use a linear programming-based method to solve the incremental graph partitioning problem. All the steps used by our method are inherently parallel and hence our approach can be easily parallelized. By using an initial solution for the graph partitions derived from recursive spectral bisection-based methods, our methods can achieve repartitioning at considerably lower cost than can be obtained by applying recursive spectral bisection from scratch. Further, the quality of the partitioning achieved is comparable to that achieved by applying recursive spectral bisection to the incremental graphs from scratch.
Starting Page	458
Ending Page	467
Page Count	10
File Format	PDF
ISBN	0818666056
ISSN	10639535
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1994-11-14
Access Restriction	Subscribed
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