Browse Prior Art Database

High Speed Multiway Branching for Microprogrammed Computers

IP.com Disclosure Number: IPCOM000081805D
Original Publication Date: 1974-Aug-01
Included in the Prior Art Database: 2005-Feb-28
Document File: 4 page(s) / 47K

Publishing Venue

IBM

Related People

Schlaeppi, HP: AUTHOR

Abstract

A common characteristic of microprograms is the presence therein of a high proportion of instructions that are associated with branches, the branching factor frequently being larger than two. While it is possible to effect multiway branches by a succession of conventional two-way branches, this technique is wasteful of machine cycles and control-store space. To overcome these disadvantages, many micro-machines have some means for implementing multiway branches.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 49% of the total text.

Page 1 of 4

High Speed Multiway Branching for Microprogrammed Computers

A common characteristic of microprograms is the presence therein of a high proportion of instructions that are associated with branches, the branching factor frequently being larger than two. While it is possible to effect multiway branches by a succession of conventional two-way branches, this technique is wasteful of machine cycles and control-store space. To overcome these disadvantages, many micro-machines have some means for implementing multiway branches.

Sequencing methods which are currently known can generally be divided into two distinct classes, i.e., implicit vs. explicit specification of the successor address by the current microinstruction.

In implicit sequencing, the successor address is computed from the current one by incrementing the contents of an instruction counter. The advantage which accrues from this technique is a short instruction. However, the disadvantages which result therefrom include a slower cycle (carry-propagation time) and the necessity of executing additional instructions, whenever the sequencing order deviates from that of the natural numbers. The implicit sequencing technique is, consequently, not appropriate where the control-store (CS) cycle is the limiting factor of the machine speed.

In explicit sequencing, the successor address is explicitly contained in the current microinstruction. The basic advantage which this technique affords is speed. However, the essential disadvantage which flows therefrom is increased CS word length. In explicit sequencing, multiway branches are effected either by providing more than one successor address, which is, of course, wasteful of CS, or by substituting the state of certain status indicators in the machine for some of the successor-address bits. The latter practice forces a fixed numerical relationship on the set of successor addresses, resulting in inflexibility with regard to CS address assignment.

The technique described herein achieves the following advantages over current methods in generating sequences of control-store addresses:
(1) It increases the speed of the execution of multiway

branches (by reducing the number of logic levels

traversed in developing the branch target address,

or in eliminating the extra control-store cycles

used for branch-table look-ups).
(2) It decreases the width of the control word required

by the branching function (by eliminating explicit

branch target addresses).
(3) It saves control-store space which is occupied by

multiway branch instructions (by eliminating

explicit branch tables).
(4) It enhances the allocation flexibility for branch

target addresses in the control store (by providing

a larger set of nontrivially different allocation

options).

1

Page 2 of 4

Although the technique is particularly advantageous when applied in microprogramming, it is also applicable on the architectural level (e.g., S/360). The technique results from the recognition that the...