Back to results

University of Victoria (Canada)

A distributed layout compactor

Abstract

dc:description.abstract

A distributed algorithm used to solve the symbolic compaction problem, running on a set of computers attached to a local area network, is presented in this thesis. The symbolic compaction problem consists of translating a symbolic description of a VLSI layout into the smallest possible mask level description without introducing any design rule violations. The compaction algorithm is based on a virtual grid approach similar to the ones used in the MULGA and VIVID systems. The serial version of the compaction algorithm is shown to have linear time complexity with respect to the number of layout primitives. Also for the benchmarks performed the compactor was 9 to 14 times faster than VIVID's compactor. The distributed algorithm developed follows the client/server model of dis­tributed systems. The client is responsible for partitioning the layout problem into separate regions to be compacted by a set of server processes, and for merger­ing these separately compacted regions into the final mask descriptions. The Dis­tributed Layout Compaction System (DLCS) thus developed was tested on three different hardware configurations with input layouts ranging in complexity from simple N AND gates to a static memory array. The benchmark results were broken up into communication time, serial time, and parallel time categories. The serial aspect of the distributed compaction algorithm required on average 40% of the real time taken to solve a problem. Thus the serial part of the algorithm limits the speed up to 2.5. The conclusion of the thesis proposes some ways of enhancing the performance of this type of distributed compaction system.

Degree

thesis:*
Level thesis:degree_level
Master of Science M.Sc.
Department thesis:degree_department
Department of Computer Science
Year dc:date.issued
1988

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Byrne, Rodrigue

Rights

dc:rights
Statement dc:rights
  • Available to the World Wide Web

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/1828/17160

Chain of custody

source
Harvested from
University of Victoria (Canada)
Base URL
dspace.library.uvic.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Byrne, Rodrigue. A distributed layout compactor. Master of Science M.Sc. thesis, 1988. https://hdl.handle.net/1828/17160