Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Multiprocessor Implementation Scheme for Graph Optimization Problems

IP.com Disclosure Number: IPCOM000035649D
Original Publication Date: 1989-Jul-01
Included in the Prior Art Database: 2005-Jan-28
Document File: 4 page(s) / 23K

Publishing Venue

IBM

Related People

Natarajan, KS: AUTHOR

Abstract

A general scheme for implementing parallel algorithms for solving a variety of graph optimization problems using a multiprocessor is described. The basic parallel processing scheme for solving the graph problems is outlined below: 1. Identify an efficient divide-and-conquer serial algorithm for solving the problem (the serial algorithm works by partitioning the input data among the subproblems). 2. Partition the data for the given problem as dictated by the divide phase of the sequential algorithm. 3. Solve several subproblems simultaneously by allocating one or more processors to each subproblem until all subproblems are solved. 4. Combine the results of the subproblems and obtain a solution to the original problem.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 36% of the total text.

Page 1 of 4

Multiprocessor Implementation Scheme for Graph Optimization Problems

A general scheme for implementing parallel algorithms for solving a variety of graph optimization problems using a multiprocessor is described. The basic parallel processing scheme for solving the graph problems is outlined below: 1. Identify an efficient divide-and-conquer serial algorithm for solving the problem (the serial algorithm works by partitioning the input data among the subproblems). 2. Partition the data for the given problem as dictated by the divide phase of the sequential algorithm. 3. Solve several subproblems simultaneously by allocating one or more processors to each subproblem until all subproblems are solved. 4. Combine the results of the subproblems and obtain a solution to the original problem.

One can implement an algorithm that attempts to improve the quality of solution found by repeating Steps 2 through 4 with different data partitionings.

The parallel implementation scheme is exemplified by describing in some detail how the Graph-Partitioning Problem can be solved. Consider the problem of partitioning a graph in K subsets using up to a maximum of K/2 processors working in parallel. The Graph-Partitioning Problem can be stated as follows: Given a graph G = (V,E) with a set V of N vertices, a set of edges E, a symmetric cost matrix C = [cij], where cij is the cost of an edge from Vertex i to Vertex j, and positive integers, W and K (>2) determine a partition of V into a set of K subsets {V1, V2, ..., VK}, such that each Vi has no more than W vertices and the cost of the partition defined below is minimized:

Such problems have a variety of applications, such as in the physical placement of circuit components in boards during physical design of electronic circuits [1], improving paging properties of programs in paged-memory computers [2] and partitioning parallel programs for execution on multiprocessors [3]. The Graph-Partitioning problem is NP-complete for W > 2 [4,p.209].

We next outline a parallel algorithm and describe the steps in some detail. 1. [Input] Read N (number of vertices), W (maximum number of vertices in a subset), K (number of subsets in a partition), and the cost matrix corresponding to the edge costs, C = [cij], 1&i&N, 1&j&N. 2. [Initialize] Choose an initial feasible partition, say S. Let S be an ordered set {V1, V2, ..., VK}. Compute the cost of partition S and call it Costold . 3. i E 1 4. [Parallel Partition] while (i&K-l & there exists an idle Processor P) do begin Mark Processor P as busy; INITIATE-TASK ( V(i), V(i+l), SEQ-PARTITION-ALGORITHM); i Ei + 2; 5. [Barrier] Wait for all parallel tasks initiated in Step 4 to finish. Let the new partition be called Snew . 6. [Compute cost] Compute the cost of partition Snew and call it Costnew . If (Costnew - Costold) = 0 then Stop else begin Costold E Costnew . S E Snew end; 7. [Randomize] Choose a random permutation Perm of the set of integers {1,2...,K}. Let Perm(i) be...