Browse Prior Art Database

DEVELOPMENT AND ANALYSIS OF A GLOBAL COMPACTION TECHNIQUE FOR MICROPROGRAMS

IP.com Disclosure Number: IPCOM000128485D
Original Publication Date: 1984-Sep-01
Included in the Prior Art Database: 2005-Sep-16

Publishing Venue

Software Patent Institute

Related People

Lah, Jehkwan: AUTHOR [+3]

Abstract

by Jehkwan Lah Chairman: Daniel E. Atkins

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 3% of the total text.

Page 1 of 55

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

THE UNIVERSITY OF MICHIGAN COMPUTING RESEARCH LABORATORY1

DEVELOPMENT AND ANALYSIS OF A GLOBAL COMPACTION TECHNIQUE FOR MICROPROGRAMS

Jehkwan Lah

CRL-TR-40-84

September 1984

Room 1079, East Engineering Building Ann Arbor, Michigan 48109 USA
Tel: (313) 763-8000

DEVELOPMENT AND ANALYSIS OF A GLOBAL COMPACTION TECHNIQUE FOR MICROPROGRAMS [ title ]

by

Jehkwan Lah

A dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy (Electrical Engineering) in The University of Michigan 1984

Doctoral Committee:

Professor Daniel E. Atkins, Chairman Professor Gideon Frieder Associate Professor Trevor Mudge Professor Norman Scott
Associate Professor Toby Teorey

ABSTRACT DEVELOPMENT AND ANALYSIS OF A GLOBAL COMPACTION TECHNIQUE FOR MICROPROGRAMS [ title ]

by

1 Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reflect the views of the funding agency.

University of Michigan Computing Research Laboratory Page 1 Sep 01, 1984

Page 2 of 55

DEVELOPMENT AND ANALYSIS OF A GLOBAL COMPACTION TECHNIQUE FOR MICROPROGRAMS

Jehkwan Lah

Chairman: Daniel E. Atkins

The need for a better microprogramming tool has increased considerably as increased demand and support of computer technology has brought about wide use of microprograms. The eventual goal of microprogramming tool development would be to make a high level microprogram language and a compiler to generate minimal- execution-time microcode for a variety of machines. In generating minimal-execution- time microcode, one aspect that differentiates microprogramming languages from macroprogramming languages is the need for compaction in highly horizontal microarchitecture.

Among the proposed microprogram compaction methods, the trace scheduling is the most general and appears to give the fastest execution of compacted microcode. However, the growth of memory size by extensive copying of blocks can be enormous, exponential in the worst case, and the complicated bookkeeping stage of the trace scheduling has been an obstacle to implementation.

A technique called beta compaction, based on trace scheduling, is proposed to mitigate the drawbacks of trace scheduling. Basically, it identifies the junction blocks (the blocks beginning with a join and ending with a conditional branch) as the major source of complication, and cut traces at those junction blocks. It achieves almost all the compaction of the trace scheduling except that which causes copying of blocks. Memory size after the beta compaction is usually smaller than the original. Even when the memory size grows in rare instances, it s bounded by O(n2) in the worst case. And the bookkeeping stage is very much simplified. The compacted microcode size variation as the source microcode changes is also very small.

A loop-free version of both beta compaction and trace schedul...