Breadcrumb

 
 

Solving layout compaction and wire-balancing problem using linear programming on the Monsoon multiprocessor

Title:

Solving layout compaction and wire-balancing problem using linear programming on the Monsoon multiprocessor

Grover, Samir (1995) Solving layout compaction and wire-balancing problem using linear programming on the Monsoon multiprocessor. Masters thesis, Concordia University.

[img]
Preview
PDF
5Mb

Abstract

The theme of this work is parallel computing for a CAD application. The layout compaction and wire-balancing problem in VLSI physical design can be formulated as a dual transshipment problem (DTP) which can be written as a linear programming problem and solved using the network dual simplex (NDS) algorithm. The goal of our work is to implement this algorithm using an implicitly parallel functional language called Id on a small shared memory Monsoon dataflow multiprocessor and study the features of this declarative language to determine quantitatively the amount of parallelism exposed in each feature. In the process, we also examine the parallelism in each phase of the application. We observed that Id's functional features (Higher-order functions, tuples, list and array comprehension, etc.) played a major role to extract the parallelism from our codes. The atomic M-structure allows processes to interact freely, hence, contributing to the parallelism. The resultant parallelism amounted to an average of 20 to 25 operations per cycle. In this thesis, we compare sequential pivoting with concurrent pivoting strategy in the NDS algorithm. From the experiments, we show that the loss of basicity after concurrent pivoting and then, retaining it makes the NDS slower due to the poor performance of the 0-token spanning-tree building method. Moreover, both pivoting strategies show almost the same amount of parallelism.

Divisions:Concordia University > Faculty of Engineering and Computer Science > Electrical and Computer Engineering
Item Type:Thesis (Masters)
Authors:Grover, Samir
Pagination:xii, 134 leaves : ill. ; 29 cm.
Institution:Concordia University
Degree Name:Theses (M.A.Sc.)
Program:Electrical and Computer Engineering
Date:1995
Thesis Supervisor(s):Hum, Herbert
ID Code:120
Deposited By:Concordia University Libraries
Deposited On:27 Aug 2009 13:09
Last Modified:08 Dec 2010 10:12
Related URLs:
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Document Downloads

More statistics for this item...

Concordia University - Footer