University of SaskatchewanHARVEST
  • Login
  • Submit Your Work
  • About
    • About HARVEST
    • Guidelines
    • Browse
      • All of HARVEST
      • Communities & Collections
      • By Issue Date
      • Authors
      • Titles
      • Subjects
      • This Collection
      • By Issue Date
      • Authors
      • Titles
      • Subjects
    • My Account
      • Login
      JavaScript is disabled for your browser. Some features of this site may not work without it.
      View Item 
      • HARVEST
      • Electronic Theses and Dissertations
      • Graduate Theses and Dissertations
      • View Item
      • HARVEST
      • Electronic Theses and Dissertations
      • Graduate Theses and Dissertations
      • View Item

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

      Thumbnail
      View/Open
      Ghatraju_Laksmikanth_1989_sec.pdf (9.767Mb)
      Date
      1989-07
      Author
      Ghatraju, Laksmikanth
      Type
      Thesis
      Degree Level
      Masters
      Metadata
      Show full item record
      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
      Master of Science (M.Sc.)
      Department
      Electrical and Computer Engineering
      Program
      Electrical Engineering
      Supervisor
      Bolton, R. J.; Abd-El-Barr, M. H.
      Copyright Date
      July 1989
      URI
      http://hdl.handle.net/10388/11617
      Collections
      • Graduate Theses and Dissertations
      University of Saskatchewan

      University Library

      © University of Saskatchewan
      Contact Us | Disclaimer | Privacy