Mikroarchitekturen und Mikroprogrammierung: Formale Beschreibung und Optimierung (Q3340110)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3874571
Language Label Description Also known as
default for all languages
No label defined
    English
    Mikroarchitekturen und Mikroprogrammierung: Formale Beschreibung und Optimierung
    scientific article; zbMATH DE number 3874571

      Statements

      0 references
      1984
      0 references
      microoperation bundle
      0 references
      microprogram
      0 references
      microinstruction encoding
      0 references
      microword length reduction
      0 references
      maximal compatibility class
      0 references
      compaction
      0 references
      resource- conflict
      0 references
      data-dependence
      0 references
      trace-scheduling
      0 references
      microprogramming high-level language
      0 references
      NP-completeness
      0 references
      Mikroarchitekturen und Mikroprogrammierung: Formale Beschreibung und Optimierung (English)
      0 references
      This textbook addresses the optimization of microprograms, which is the ''hot'' research area in the design of microprogrammed control units. The optimization of microprograms means here a reduction of overall microprogram size, which should involve the shortening of microprogram execution time. The space/time microcode optimization procedures are in general required in order to improve firmware implementation quality and productivity. In particular, their use is absolutely necessary in microprogram design aids. The requirements put on their effectiveness and practical usage will certainly grow considerably to utilize fully the possibilities offered by VLSI technologies. The minimal solution optimization procedures are known to be NP-complete, thus hard to practical applications. This is the reason why near-optimal procedures of less complexity have to be elaborated. The book surveys a number of optimization procedures, which are divided into two classes. In the first of them the goal is to minimize or reduce the microinstruction word length, while in the second the reduction of the number of microinstructions in the microprogram is under consideration. The first chapter of the book introduces the reader to the microprogrammed control units and their characteristics - structures, microoperations and micro-instructions, encoding, parallelism, pipelining and vertical migration of functions. The microoperations are formally described by a 6-tuple containing the name of the microoperation, the set of input storage elements, the set of output storage elements, the set of functional units, the enumeration of clock phases, in which the microoperation is executed and the set of microinstruction fields which control this microoperation. Comprehensive terminology and definitions of the relevant notions are given, of which notions concerning compatibility classes of microoperations, data-dependence and resource-conflicts are of greatest importance. In the second chapter the algorithms for the microinstruction word length reduction are surveyed. These algorithms use code fields in the microinstruction related to the maximal compatibility classes of microoperations. Such encoding preserves the logical interpretation of the fields of the microinstruction. Twofold solutions to encoding problems are obtained by formulating them as a covering problem (known in the switching theory) and a linear programming method. The third chapter surveys algorithms for the reduction of the number of microinstructions in microprograms, also called the compaction algorithms, which are based on the data-dependency and resource-conflicts analysis. The key role plays the notion of the straight-line microcode section (SLM), which is an ordered collection of microoperations with no entry points, except at the beginning, and no branches, except possibly at the end. The SLM boundaries serve for distinguishing between local and global compaction. The book describes 4 algorithms for the local compaction, i.e. the compaction within the SLM, namely minimal branch- and-bound, non-minimal branch-and-bound with heuristics, critical path and first-come-first-serve algorithms. The algorithms for global compaction have been divided into two groups - block-oriented and trace- scheduling algorithms. In the fourth chapter of the book the high-level languages for microprogramming are concisely discussed. One remark concerning terminology is needed. The term ''microarchitecture'' means here the architecture of microprogrammed control unit (i.e. the image of the computer seen by the microprogrammer) and should not be confused with the architecture of microcomputers or microprocessors (i.e. the image of the microcomputer seen by the programmer). To conclude - although the subject matter of this book is far from maturity now and requires much more research, the book is very valuable because it systematizes the optimization area of microprogramming from the optimization point of view, presents a comprehensive terminology, gives formal and theoretical background for optimization procedures and presents these procedures in a unified manner.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references