Patent GB-1221023-A (GB)
Title: Data processing apparatus
IPC: G06F9/38
Filed: 1968-12-17
Abstract: 1,221,023. Data processing. INTERNATIONAL BUSINESS MACHINES CORP. 17 Dec., 1968 [15 Jan., 1968], No. 59924/68. Heading G4A. Stored-programme data processing apparatus uses an advance branch instruction in the instruction sequence prior to the branch point, the address of the branch point being extracted from the advance branch instruction and compared with the addresses of subsequent instructions accessed. Branch and instruction look-ahead.-An " advance branch " instruction, placed in the instruction sequence ahead of the branch point, contains the op code, a " from " field specifying the address of the last instruction to be executed before branching (assuming the latter takes place), a " to " field specifying the address of the instruction to be branched to, a 4-bit " mask " field, a " retain " bit and an " immediate comparison " bit. The instructions are fetched from memory and supplied via a look ahead tree of registers to the processor where they are decoded and executed. If an " advance branch " instruction, when decoded, has its " immediate comparison " bit at 1, each bit of its " mask " field is ANDed with the corresponding bit of a 4-bit condition code in the processor and if all the results are 0 the instruction is discarded. If any result is 1, all the " mask " bits are set to 1 (to subsequently cause an unconditional branch, see below). In this case and also if the " immediate comparison " bit is 0, the " from," " to," " mask " and " retain " fields of the instruction are inserted into the first free location of an associative memory. The look-ahead tree has a " branch " and a " no branch " sub-tree. Each sub-tree has first, second and third levels with 1, 2 and 4 registers respectively, each register having space for an instruction, and its memory address, and half the registers also having space for a " mask " field. When the processor requires the next instruction it obtains it from the first level of the " branch " or " no branch " sub-tree according as a branch is to be made or not at this point, this being determined by ANDing each bit of the " mask " field in the first level of the " branch " sub-tree with the corresponding bit of the condition code, the branch being taken if any result is 1. According as the branch is taken or not, the " branch " or " no branch " sub-tree respectively is shifted up, half the registers in each of the second and third levels of the selected sub-tree feeding corresponding registers in the first and second levels respectively of the same sub-tree and half feeding similar registers in the first and second levels of the other sub-tree. Instruction addresses in the second level of the tree are used for associative matching on the " from " fields of the associative memory, the corresponding " to " and " mask " fields from the latter being inserted into some registers of the third level of the tree. Other registers of this level receive instruction addresses from the second level, after incrementation. Instruction addresses in the third level are used to fetch the corresponding instructions from memory for insertion into the tree in the same registers as their addresses (each address returns with its instruction and is compared with the addresses in the tree to find the correct location). However, unnecessary instruction fetches (corresponding to branches and non-branches which will never be taken) are avoided in response to the " mask " fields stored in the first and second levels since a mask of 0000 corresponds to a branch which will never be taken and a mask of 1111 corresponds to an unconditional branch. If the " retain " bit of an " advance branch " instruction is 1, the fields from it are restored into the associative memory with an associated " in use " bit at 1 after reading from the associative memory on a successful match on the " from " field (see above), otherwise tney are effectively deleted by restoring them with the " in use " bit set to 0. The " retain " feature permits an instruction loop to be executed more than once. Overloading of the associative memory is prevented by, every time portions of an " advance branch " instruction are stored (or restored with " in use " at 1), storing the contents of a cycle counter with them. Every time the cycle counter, which is cyclic with 8 possible states, is incremented, the " in use " bits of stored items having the new value of the cycle counter, are set to 0. The tree is reloaded from scratch at system start or after an interrupt or after an ordinary branch instruction. Modifications.-In the above, the decision as to whether the branch is to be taken is effectively made when the " advance branch " instruction is decoded or at the branch point, according to the value of the " immediate comparison " bit, but a further field in the instruction could permit it to be made at any specified intermediate point. Branching may be made conditional on an index value. The " from " and " to " addresses may be relative to that of the " advance branch " instruction. " To " addresses may be relative to " from" addresses. The " from " and " to " addresses may be indexable. The " retain " field may be replaced by a count field to specify the number of times the branch is to be taken. More than one " advance branch " instruction may have the same " from " address, if tags indicating precedence are used. Overloading of the associative memory could be prevented by logic for clearing unused branches, or by discarding the oldest unused entry when full. Four or five or more levels could be provided in the tree.