Back to results

University of Saskatchewan

DESIGN AND IMPLEMENTATION OF A VLSI SYSTOLIC ARRAY FOR THE TRANSPORTATION SIMPLEX ALGORITHM

Abstract

dc:description.abstract

The increasing demand for high speed and improved performance in modern signal and image processing applications, and the availability of low-cost, high-density, high-speed VLSI devices have facilitated the design and implementation of massively parallel processors. The decreasing hardware cost and the emerging computer-aided design facilities have inspired many innovative designs in array processor architecture. One of the important advances in array processor architecture is the "systolic architecture". In this thesis, a design of a systolic array for the transportation simplex algorithm is proposed. The transportation problem is one of the most important linear programming problems. It is a general problem of allocating limited resources among competing activities in an optimal way. A basic systolic cell design for the transportation matrix array of size n x m is presented. A simulator for the transportation simplex algorithm was written to verify the proposed design and architecture. The initial basic feasible solution was obtained using Russell's approximation method. Another algorithm to obtain the initial basic feasible solution to the transportation problem based on the "greedy" approach is proposed. The hardware implementation of the basic cell was carried out using the QUISC silicon compiler and the associated standard cell library. The fabricated chips were found to be operational as expected at a maximum operational speed of 10 MHz.

Degree

thesis:*
Name thesis:degree_name
Master of Science (M.Sc.)
Level thesis:degree_level
Masters
Discipline thesis:degree_discipline
Electrical Engineering
Department thesis:degree_department
Electrical and Computer Engineering
Grantor
University of Saskatchewan
Year dc:date.issued
1989

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Ghatraju, Laksmikanth
Advisors dc:contributor.advisor
  • Bolton, R. J.
  • Abd-El-Barr, M. H.

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/10388/11617

Chain of custody

source
Harvested from
University of Saskatchewan
Base URL
harvest.usask.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Ghatraju, Laksmikanth. DESIGN AND IMPLEMENTATION OF A VLSI SYSTOLIC ARRAY FOR THE TRANSPORTATION SIMPLEX ALGORITHM. Masters thesis, University of Saskatchewan, 1989. https://hdl.handle.net/10388/11617