Integrated local and global microprogram reduction Public Deposited

http://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/wm117r934

Descriptions

Attribute NameValues
Creator
Abstract or Summary
  • Compaction of a horizontal microprogram is an attempt to exploit fully the parallelism permitted by a given algorithm and data processing structure in order to produce a short microprogram. B oth viewpoints of the problem: the local compaction viewpoint which deals with compaction within a straight-line segment, or a basic block; and the global compaction viewpoint which deals with compaction across basic blocks are explored. This dissertation is presented as a composite of three papers addressing these viewpoints. The first paper models the interactions of data dependencies with resource limitations in a manner which allows the designer to select the compaction algorithm best suited to the problem architecture and design goals. A comp o site graph model of the problem is shown to support a range of local compaction models and methods. Optimal solution searches and faster heuristic-based compactions are supported by the composite graph. The second paper describes a global compaction technique called KLITS, which is a heuristic iteration of microoperati on movements. This technique can accommodate any of several measures of optimization, and retains the block structure of the original. KLITS searches for globally profitable sequences of rnicrooperation movements even when the first few movements of some sequences do not yield immediate profit. Performance on some previously published example microprograms is encouraging. The third paper describes tests of the KLITS algorithm. Microprograms are modelled as pseudo-microprograms. Both pseudo-microprogram generation and KLITS global compaction are implemented. For each pseudo-microprogram generated, both local compaction and the KLITS global compaction technique are applied. As the number of basic blocks in a pseudo-microprogram increases, the pseudo-microprogram compacted by the KLITS algorithm increasingly becomes more compact than one compacted by local compaction. The experiments also suggest that the compaction time grows slowly enough for the algorithm to be used practically.
Resource Type
Date Available
Date Copyright
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Committee Member
Academic Affiliation
Non-Academic Affiliation
Subject
Rights Statement
Peer Reviewed
Language
Digitization Specifications
  • File scanned at 300 ppi (Monochrome) using Capture Perfect 3.0.82 on a Canon DR-9080C in PDF format. CVista PdfCompressor 4.0 was used for pdf compression and textual OCR.
Replaces
Additional Information
  • description.provenance : Submitted by Kim Stowell (ksscannerosu@gmail.com) on 2013-05-30T23:10:03Z No. of bitstreams: 1 SiriboonThit1988.pdf: 1410518 bytes, checksum: 55dd7c71dc2fd9faaeedac2aaf69294f (MD5)
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2013-05-31T02:16:16Z (GMT) No. of bitstreams: 1 SiriboonThit1988.pdf: 1410518 bytes, checksum: 55dd7c71dc2fd9faaeedac2aaf69294f (MD5)
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2013-06-28T23:00:44Z (GMT) No. of bitstreams: 1 SiriboonThit1988.pdf: 1410518 bytes, checksum: 55dd7c71dc2fd9faaeedac2aaf69294f (MD5)
  • description.provenance : Made available in DSpace on 2013-06-28T23:00:44Z (GMT). No. of bitstreams: 1 SiriboonThit1988.pdf: 1410518 bytes, checksum: 55dd7c71dc2fd9faaeedac2aaf69294f (MD5) Previous issue date: 1988-03-11

Relationships

In Administrative Set:
Last modified: 08/10/2017

Downloadable Content

Download PDF
Citations:

EndNote | Zotero | Mendeley

Items